CSC 143 Challenge Project Rubik\'s Cube Background Rubik\'s Cube is a mecahnical
ID: 3778307 • Letter: C
Question
CSC 143 Challenge Project Rubik's Cube Background Rubik's Cube is a mecahnical puzzle that was designed bythe architect Erno Rubik. The design consists of a cube composed of 9tiles on each face, these faces belong to sub-cubes, cubies," of which there are 26. In its solved state the cube has a different color on each face (typically red, orange, green, blue, white, and yellow.) The cube is mechanically designed so that each face can rotate independently, allowing the cubies to become scrambled. The puzzle became as a children' toy in the 1980s, and speed-solving the Rubik's Cube became pasttime; the world record Rubik's Cube speed-solve cuITently stands at less than 6 seconds today, acco mplished by a Dutch engineer. The Problem Your final project problem is to implement a computer program that will solve a Rubik's Cube, and to profile your code to quantify its complexity. Your program should be able to read an input file containing a random Rubik's Cube configuration (the input file will specify the 3x3 color matrix for the top, bottom, left, right, front, and back faces of the cube, and output a sequence of moves that will result in a s olved Rubik's Cube (solid color on each face). To indicate rotational transformations, your program should print a sequence of moves to achieve a solution, using the following standard notation: Rotate the front face clockwise Rotate the front face counter-clockwise Rotate the back face counter-clockwiis Up Rotate the top face counter-clockwise Rotate the back face clockwise Rotate the top face clockwise Rotate the bottom face clockwise Rotate the bottom face counter-clockwise Rotate the right face clockwise Rotate the right face counter-clockwis Rotate the left face clockwise Rotate the left face counter-clockwisExplanation / Answer
import orbital.algorithm.template.*;
import orbital.logic.functor.Function;
import orbital.logic.functor.MutableFunction;
import orbital.math.*;
import java.util.*;
import java.util.zip.*;
import java.io.*;
import java.text.*;
import java.awt.Color;
import util.Basic;
public class RubiksCube implements GeneralSearchProblem {
public static final int MAX_STEPS = 16;
public static final int RANDOM = 0;
public static final int COMPLEX = 1;
public static final int STANDARD = 2;
public static int SEQUENCE = RANDOM;
private static final boolean RESTRICT_TO_CANONICAL_ACTIONS = true;
public static final int SIZE = 2;
public static void main(String arg[]) throws Exception {
DateFormat df = new SimpleDateFormat("H:mm:ss:S");
df.setTimeZone(TimeZone.getTimeZone("Greenwich/Meantime"));
Date loadeta;
Function h;
try {
File databaseFile = new File(RubiksCubeCreatePattern.patternDatabaseFile);
if (!databaseFile.exists()) {
System.err.println("File "" + databaseFile + "" does not exist. Will create one.");
RubiksCubeCreatePattern.main(arg);
}
System.out.println("Loading");
long loading = System.currentTimeMillis();
InputStream fis = new FileInputStream(databaseFile);
if (RubiksCubeCreatePattern.compressed)
fis = new InflaterInputStream(fis);
ObjectInputStream is = new ObjectInputStream(fis);
final int patternDepth = is.readInt();
final Map patternDatabase = (Map) is.readObject();
is.close();
h = new Function() {
final Real UNDERESTIMATE = Values.getDefaultInstance().valueOf(patternDepth + 1);
public Object apply(Object o) {
return UNDERESTIMATE;
}
};
h = new HeuristicAlgorithm.PatternDatabaseHeuristic(h, patternDatabase);
loadeta = new Date(System.currentTimeMillis() - loading);
System.out.println("Completed loading " + df.format(loadeta));
if (patternDepth != RubiksCubeCreatePattern.MAX_STEPS) {
System.out.println("Warning: File "" + databaseFile + "" does not seem up to date. Consider calling");
System.out.println(" java RubiksCubeCreatePattern");
System.out.println("to re-create "" + databaseFile + "".");
}
} catch (IOException x) {
System.err.println(x);
System.err.println("Make sure that the pattern database file has been created by calling");
System.err.println(" java RubiksCubeCreatePattern");
return;
}
System.out.println("Start");
long start = System.currentTimeMillis();
GeneralSearch s;
Cube solution = (Cube) s.solve(new RubiksCube(SIZE));
Date eta = new Date(System.currentTimeMillis() - start);
console.color(Color.white);
if (solution != null) {
System.out.println("Found: " + solution + " ");
printcubus(solution.feld, 2, 30);
console.color(Color.white);
console.LOCATE(4, 9);
console.print("total accumulated cost of " + NumberFormat.getInstance().format(solution.accumulatedCost) + " steps", false);
} else {
System.out.println("NO solution");
console.LOCATE(30, 2);
console.print("NO solution");
}
console.LOCATE(4, 10);
console.print("Duration " + df.format(eta), false);
console.LOCATE(4, 11);
console.print("Load Time " + df.format(loadeta), false);
}
public static final int left = 0;
public static final int back = 1;
public static final int top = 2;
public static final int front = 3;
public static final int right = 4;
public static final int down = 5;
private static final String names[] = {
"L", "B", "T", "F", "R", "D"
};
public static final int orange = 0;
public static final int blue = 1;
public static final int yellow = 2;
public static final int white = 3;
public static final int red = 4;
public static final int green = 5;
private static final Color colors[] = {
Color.orange.darker(), Color.blue, Color.yellow.brighter(), Color.white, Color.red, Color.green
};
protected final int size;
private final Cube _initialState;
public RubiksCube(int size) {
if (size != 2)
throw new InternalError("only implemented for size 2");
this.size = size;
this._initialState = constructInitialState();
}
private Cube constructInitialState() {
Cube c = new Cube(size, 0.0);
switch (SEQUENCE) {
case COMPLEX:
c.feld[16] = blue;
c.feld[6] = yellow;
c.feld[9] = red;
c.feld[10] = red;
c.feld[19] = white;
c.feld[13] = yellow;
break;
case STANDARD:
c.drehe(2, -1); c.drehe(2, -1); c.drehe(1, 1); c.drehe(2, 1);
break;
case RANDOM:
{
Random random = new Random();
final int MIN_ACTION =
RESTRICT_TO_CANONICAL_ACTIONS
? front
: left;
for (int i = 0; i < MAX_STEPS; i++) {
int side = MIN_ACTION + random.nextInt(down - MIN_ACTION + 1);
int direction = -1 + 2 * random.nextInt(2);
c.drehe(side, direction);
}
System.out.println(c + " of maximum depth " + MAX_STEPS);
}
break;
default:
throw new IllegalStateException(SEQUENCE + " is an illegal mode for SEQUENCE");
}
c.clearActionLog();
return c;
}
public Object getInitialState() {
System.out.println(_initialState + " to be solved. ");
printcubus(_initialState.feld, 2, 2);
return _initialState.clone();
}
public boolean isSolution(Object n) {
Cube c = (Cube) n;
if (c.isGood()) {
System.out.println("Solution: " + n);
return true;
}
return false;
}
public Iterator actions(Object n) {
Cube s = (Cube) n;
List ex = new LinkedList();
final int MIN_ACTION =
RESTRICT_TO_CANONICAL_ACTIONS
? front
: left;
for (int side = MIN_ACTION; side <= down; side++)
for (int dir = -1; dir <= 1; dir += 2) {
Cube t = (Cube) s.clone();
t.drehe(side, dir);
ex.add(t);
}
return ex.iterator();
}
public final Iterator states(Object action, Object state) {
return Collections.singleton(action).iterator();
}
public TransitionModel.Transition transition(Object action, Object state, Object statep) {
return new Transition(action, 1);
}
public MutableFunction getAccumulatedCostFunction() {
return _accumulatedCostFunction;
}
private static final MutableFunction _accumulatedCostFunction = new MutableFunction() {
public Object apply(Object state) {
return ((Cube)state).accumulatedCost;
}
public Object set(Object state, Object newAccumulatedCost) {
Object old = ((Cube)state).accumulatedCost;
((Cube)state).accumulatedCost = (Real)newAccumulatedCost;
return old;
}
public Object clone() {
throw new UnsupportedOperationException();
}
};
protected static class Cube {
private int[] feld;
private Real accumulatedCost;
private StringBuffer actionLog;
private Cube(int[] field, Real accumulatedCost, StringBuffer actionLog) {
if (field.length != 2 * 2 * 6)
throw new InternalError("not implemented for size " + Math.sqrt(field.length / 6.0));
this.feld = field;
this.accumulatedCost = accumulatedCost;
clearActionLog();
}
public Cube(int size, Real accumulatedCost) {
this(new int[size * size * 6], accumulatedCost, new StringBuffer());
if (size != 2)
throw new InternalError("not implemented for size " + size);
for (int i = 0; i < 4; i++)
feld[i] = orange;
for (int i = 4; i < 8; i++)
feld[i] = blue;
for (int i = 8; i < 12; i++)
feld[i] = yellow;
for (int i = 12; i < 16; i++)
feld[i] = white;
for (int i = 16; i < 20; i++)
feld[i] = red;
for (int i = 20; i < 24; i++)
feld[i] = green;
}
public Cube(int size, double accumulatedCost) {
this(size, Values.getDefaultInstance().valueOf(accumulatedCost));
}
public Object clone() {
return new Cube((int[]) feld.clone(), accumulatedCost, actionLog);
}
public boolean equals(Object o) {
if (!(o instanceof Cube))
return false;
Cube b = (Cube) o;
if (feld.length != b.feld.length)
return false;
for (int i = 0; i < feld.length; i++)
if (feld[i] != b.feld[i])
return false;
return true;
}
public int hashCode() {
int hash = 0;
int shift = 0;
for (int i = 0; i < feld.length; i++) {
hash |= feld[i] << shift;
if ((shift += 3) + 2 >= 32)
shift -= 32 - 2;
}
return hash;
}
public String toString() {
return MathUtilities.format(feld) + " for total accumulated cost " + accumulatedCost + " moves that lead here: " + actionLog;
}
public boolean isGood() {
for (int i = 0; i < feld.length; i = i + 4) {
if (!(feld[i] == feld[i + 1] && feld[i] == feld[i + 2] && feld[i] == feld[i + 3]))
return false;
}
return true;
}
public void drehe(int side, int direction) {
switch (side) {
case left: // 'left - okay
reihentausch(0, 1, 2, 3, direction);
reihentausch(8, 12, 22, 4, direction);
reihentausch(11, 15, 21, 7, direction);
break;
case back: // 'back
reihentausch(4, 5, 6, 7, direction);
reihentausch(1, 21, 17, 9, direction);
reihentausch(0, 20, 16, 8, direction);
break;
case top: // 'top
reihentausch(8, 9, 10, 11, direction);
reihentausch(1, 6, 19, 12, direction);
reihentausch(2, 7, 16, 13, direction);
break;
case front: // 'front
reihentausch(12, 13, 14, 15, direction);
reihentausch(3, 11, 19, 23, direction);
reihentausch(2, 10, 18, 22, direction);
break;
case right: // 'right
reihentausch(16, 17, 18, 19, direction);
reihentausch(9, 5, 23, 13, direction);
reihentausch(10, 6, 20, 14, direction);
break;
case down: // 'down
reihentausch(20, 21, 22, 23, direction);
reihentausch(5, 0, 15, 18, direction);
reihentausch(4, 3, 14, 17, direction);
break;
default:
throw new InternalError("unknown side " + side);
}
logAction(side, direction);
}
protected void reihentausch(int a, int b, int c, int d, int direction) {
int temp = feld[a];
switch (direction) {
case -1: // counter-clockwise
feld[a] = feld[b];
feld[b] = feld[c];
feld[c] = feld[d];
feld[d] = temp;
break;
case 1: // clockwise
feld[a] = feld[d];
feld[d] = feld[c];
feld[c] = feld[b];
feld[b] = temp;
break;
default:
throw new InternalError("unknown direction " + direction);
}
}
private void logAction(int side, int direction) {
actionLog.append(',');
actionLog.append(names[side]);
if (direction >= 0)
actionLog.append('+');
actionLog.append(direction);
}
public void clearActionLog() {
actionLog = new StringBuffer();
}
}
private static Basic console = null;
protected static void printcubus(int feld[], int y, int x) {
if (console == null)
Basic.show(console = new Basic(40, 10), true, true);
String f = "#";
if (x == 0 || y == 0) {
y = console.CSRLIN();
x = console.POS(0);
if (y > 19) {
console.inkey();
console.cls();
x = y = 1;
}
}
console.LOCATE(x + 2 * f.length(), y);
console.color(colors[feld[4]]);
console.print(f, false);
console.color(colors[feld[5]]);
console.print(f, false);
console.LOCATE(x + 2, y + 1);
console.color(colors[feld[7]]);
console.print(f, false);
console.color(colors[feld[6]]);
console.print(f, false);
console.LOCATE(x, y + 2);
for (int i = 0; i < 17; i += 8) {
console.color(colors[feld[i]]);
console.print(f, false);
console.color(colors[feld[i + 1]]);
console.print(f, false);
}
console.color(colors[feld[20]]);
console.print(f, false);
console.color(colors[feld[21]]);
console.print(f, false);
console.LOCATE(x, y + 3);
for (int i = 3; i < 20; i += 8) {
console.color(colors[feld[i]]);
console.print(f, false);
console.color(colors[feld[i - 1]]);
console.print(f, false);
}
console.color(colors[feld[23]]);
console.print(f, false);
console.color(colors[feld[22]]);
console.print(f, false);
console.LOCATE(x + 2 * f.length(), y + 4);
console.color(colors[feld[12]]);
console.print(f, false);
console.color(colors[feld[13]]);
console.print(f, false);
console.LOCATE(x + 2, y + 5);
console.color(colors[feld[15]]);
console.print(f, false);
console.color(colors[feld[14]]);
console.print(f);
}
}