Motivation: I was eating at Cracker Barrel with my friend Rene Simon from Gainesville, and we talked about this Peg game they have at each table (maybe another little for fun project). I thought about how I can probably work out how to write a program in Prolog for that game, and I said prolog can be used to solve many mini games, and he mentioned a Rubiks Cube. I said I can prolly work it out from all the Prolog programming I've done in Dr. Geoff Sutcliffe's courses. So I said sure, why not. But then he only knows JAVA, so I said sure I'll try to work this out in java, without the help of all the back track help of PROlog. So my goal is to get an easy to understand A* approach to solve this program using java as the programming language. Maybe even create an applet to show how it solves a Rubiks Cube visually. Being that I have never been able to solve the darn thing, I hope this program can do it for me. Future Goals: Maybe program the human strategy approach instead of A* (solve in parts).

Notes:

There are 27 'MiniCubes' in a RubikCube: 8 are Corner MCs, (three sides) 12 are Edge MCs, (only two sides) 6 are Center MCs, (stationary) 1 is Core MC. (Core is useless to record)

A few ways to do it: - Strategy (like a human would do it) Human Strategy - Brute Force (Try all moves possible, DFS, BFS approaches) - Using a search algorithm with heuristics (e.g. A*) A* with rubik cube, but in prolog (WORKING OFF THIS MODEL)

I will focus on using A*, using heuritics, g(n) would be the number of moves so far h(n) would be number of colors off each state is from goal state

Before an example, an explanation on the Minicube: Each minicube has 6 sides (U, D, L, R, F, B) Up, Down, Left, Right, Front, Back FOr a Corner MC, 3 colors are affected, for example MC1 is the corner with upper, front, and left (*,_,*,_,*) if upper was white, front was red, and left was blue then: (w,_,b,_,r,_), other 3 sides are null So for heuristic value, there are 2 values: - rot(mc) How many rotations minimum to return to right position - off(mc)How many colors are off

If one color is correct, while two are not, then, for the two that are not correct, count how many sides away is the correct color off(mc) = off(c1) + off(c2) + occ(c3), for a corner off(mc) = off(c1) + off(c2), for an edge

For rotations: Corners: They can only be 1, 2, or 3 rotations away Edges: They can oly be 1, 2, or 3 rotations away as well

Each rotation away counts as .5 of a value, so 3 rotations away is 1.5

so total h(n) = rot(mc1) + off(mc1) + rot(mc2) + off(mc2) + ...

A minicube can be at the correct location, but in the wrong order, for example: MC1 again, with (w,_,b,_,r,_) as the correct goal state of this cube It can be in the same position again (same 3 colors are colored) (NOTE: no other MC can have the exact same 3 sides colored, no matter what color) other two states are (b,_,r,_,w,_) or (r,_,w,_,b,_) score for former is 3, and latter is 3 (each color is 1 side away from correct side of the color) (NOTE: state(r,_,b,_,w,_) is INVALID and impossible with (w,_,b,_,r,_) as the goal state, for the minicube was somehow mis-labeled in input)

SO for A*, have an open set and closed set

open set intially just initial state, closed set is {}

move best state over to closed set, and generate all possible next states from ths best state

check to make sure each of these next states are better than what is in the open set or closed set

if there are better ones in the open or closed set, then discard this next state, NO USE FOR IT