MagicCubeNdSolve
|
||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||
java.lang.Object
public class MagicCubeNdSolve
Solves the d-dimensional analogue of Rubik's cube.
Can solve 2d and 3d puzzles
for any number of dimensions d ≥ 3.
Simplest programmatic usage:
String solution = MagicCubeNdSolve.solve(
" AAa AAa AAa "
+ " bBB c C c C c C Bbb "
+ " BBB C c C c C c bbb "
+ " bBB C c C c C c Bbb "
+ " Aaa Aaa Aaa "
);
System.out.println("Solution = \""+solution+"\"");
which prints this:
Solution = "aBC aBC ABC ABC cBA cBA ABC ABC cBA cBA aCB aCB"
In your string representation of the puzzle state,
you can represent the colors by any 2*d distinct non-space characters.
List the stickers in order by the current coordinates of their centers,
lexicographically. The format is totally free form;
you can add spaces and newlines wherever you feel like it (as above),
or omit them altogether:
"AAaAAaAAabBBcCcCcCBbbBBBCcCcCcbbbbBBCcCcCcBbbAaaAaaAaa"
Each move in the solution is a 90 degree twist of a face, represented by a 3-letter sequence:
That's it!
Here are all the public static functions:
String newPuzzle(int n, int d)
boolean isSane(String puzzleString)
boolean isSolvable(String puzzleString)
- equivalent to isSolvable(puzzleString, ~0, ~0, null 0)
boolean isSolved(String puzzleString)
String solve(String puzzleString)
- equivalent to solve(puzzleString, ~0, ~0, null, 0)
String solve(String puzzleString,
int whichToPosition,
int whichToOrient,
java.io.PrintWriter progressWriter,
int debugLevel)
String apply(String moves, String puzzleString)
String scramble(String puzzleString,
int minScrambleChen,
int maxScrambleChen,
java.util.Random generator)
int n(String puzzleString)
int d(String puzzleString)
void main(String args[]) - full featured test/demo program
void simple_main(String args[]) - simple test/demo program
void trivial_main(String args[]) - trivial test/demo program
For descriptions of these functions, use javadoc
(run "javadoc MagicCubeNdSolve.java", which will create a bunch of html
files in the current directory, including index.html)
or see the descriptions above each function
(search for the string PUBLIC in the source file).
AAA AAA AAA
BBB C c C c C c bbb
BBB C c C c C c bbb
BBB C c C c C c bbb
aaa aaa aaa
and after the single twist "ACB"
(i.e. twist face A 90 degrees from axis C to axis B):
AAA AAA AAA
CCC b B b B b B ccc
BBB C c C c C c bbb
BBB C c C c C c bbb
aaa aaa aaa
Note that the twist ACB can also be expressed as ABc or Acb or AbC.
Here's a pristine 34 puzzle:
AAA AAA AAA
AAA AAA AAA
AAA AAA AAA
BBB BBB BBB
CCC D d D d D d ccc
CCC D d D d D d ccc
CCC D d D d D d ccc
bbb bbb bbb
BBB BBB BBB
CCC D d D d D d ccc
CCC D d D d D d ccc
CCC D d D d D d ccc
bbb bbb bbb
BBB BBB BBB
CCC D d D d D d ccc
CCC D d D d D d ccc
CCC D d D d D d ccc
bbb bbb bbb
aaa aaa aaa
aaa aaa aaa
aaa aaa aaa
and a pristine 35 puzzle (make your window wide):
AAA AAA AAA AAA AAA AAA AAA AAA AAA
AAA AAA AAA AAA AAA AAA AAA AAA AAA
AAA AAA AAA AAA AAA AAA AAA AAA AAA
BBB BBB BBB BBB BBB BBB BBB BBB BBB
CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc
CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc
CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc
bbb bbb bbb bbb bbb bbb bbb bbb bbb
BBB BBB BBB BBB BBB BBB BBB BBB BBB
CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc
CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc
CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc
bbb bbb bbb bbb bbb bbb bbb bbb bbb
BBB BBB BBB BBB BBB BBB BBB BBB BBB
CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc
CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc
CCC CCC CCC DDD E e E e E e ddd DDD E e E e E e ddd DDD E e E e E e ddd ccc ccc ccc
bbb bbb bbb bbb bbb bbb bbb bbb bbb
aaa aaa aaa aaa aaa aaa aaa aaa aaa
aaa aaa aaa aaa aaa aaa aaa aaa aaa
aaa aaa aaa aaa aaa aaa aaa aaa aaa
| Method Summary | |
|---|---|
static java.lang.String |
apply(java.lang.String movesString,
java.lang.String puzzleString)
Applies the given move sequence to the puzzle, returning a new puzzle string with the same formatting as the input puzzleString. |
static int |
d(java.lang.String puzzleString)
Returns the number of dimensions d of the nd puzzle. |
static boolean |
isSane(java.lang.String puzzleString)
Tells whether the given string represents an nd puzzle for some n, d (possibly taken apart and put back together wrong, possibly with some corners inside out). |
static boolean |
isSolvable(java.lang.String puzzleString)
Tells whether the given (assumed to be sane) puzzle string is solvable. |
static boolean |
isSolvable(java.lang.String puzzleString,
int whichToCheckPositions,
int whichToCheckOrientations,
java.io.PrintWriter progressWriter,
int debugLevel)
Tells whether the given (assumed to be sane) puzzle string is solvable. |
static boolean |
isSolved(java.lang.String puzzleString)
Tells whether the given (assumed to be solvable) puzzle string is already solved. |
static void |
main(java.lang.String[] args)
Full featured test/demo program. |
static int |
n(java.lang.String puzzleString)
Returns the length n of the nd puzzle. |
static java.lang.String |
newPuzzle(int n,
int d)
Returns a string representing a pristine nd puzzle, formatted nicely with A,B,C,... |
static java.lang.String |
readPuzzle(java.io.BufferedReader reader,
int debugLevel)
Reads a puzzle string. |
static java.lang.String |
reformatPuzzleString(java.lang.String puzzleString,
java.lang.String template)
Reformats the non-space chars of puzzleString to look like template. |
static java.lang.String |
scramble(java.lang.String puzzleString,
int minScrambleChen,
int maxScrambleChen,
java.util.Random random,
int debugLevel)
Returns a random number from minScrambleChen to maxScrambleChen of random 90-degree twists that can be applied to the given puzzle (see apply). |
static void |
simple_main(java.lang.String[] args)
Simple test/demo program. |
static java.lang.String |
solve(java.lang.String puzzleString)
Solves the puzzle. |
static java.lang.String |
solve(java.lang.String puzzleString,
int whichToPosition,
int whichToOrient,
java.io.PrintWriter progressWriter,
int debugLevel)
Solves the puzzle. |
static void |
trivial_main(java.lang.String[] args)
Trivial test/demo program. |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Method Detail |
|---|
public static java.lang.String newPuzzle(int n,
int d)
Throws an Error if n,d are ridiculous.
public static java.lang.String reformatPuzzleString(java.lang.String puzzleString,
java.lang.String template)
Throws an Error if puzzleString and template have a different number of non-space chars; does no other sanity checking on puzzleString.
public static boolean isSane(java.lang.String puzzleString)
public static boolean isSolvable(java.lang.String puzzleString)
Equivalent to isSolvable(puzzleString, ~0, ~0, null, 0).
public static boolean isSolvable(java.lang.String puzzleString,
int whichToCheckPositions,
int whichToCheckOrientations,
java.io.PrintWriter progressWriter,
int debugLevel)
whichToCheckPositions and whichToCheckOrientations should be bit masks representing which cubie types (i.e. number of stickers per cubie) to check permution parity of and which to check orientation parity of, respectively; whichToOrient must be a subset of whichToPosition.
Throws an Error if the puzzle string is insane
(see isSane)
or if there are any bits set in whichToCheckPositions
which are not also set in whichToCheckOrientations.
Currently also throws an Error if n > 3.
public static boolean isSolved(java.lang.String puzzleString)
Throws an Error if the puzzle is insane
(see isSane).
If n > 3 it may return a result (which may be taken as definitive) or may throw an Error, since it may not be completely implemented.
public static java.lang.String solve(java.lang.String puzzleString)
Equivalent to solve(puzzleString, ~0, ~0, null, 0).
public static java.lang.String solve(java.lang.String puzzleString,
int whichToPosition,
int whichToOrient,
java.io.PrintWriter progressWriter,
int debugLevel)
whichToPosition and whichToOrient should be bit masks representing which cubie types (i.e. number of stickers per cubie) to position and which to orient, respectively; whichToOrient must be a subset of whichToPosition.
Progress messages and stats will be written to progressWriter if it is not null.
If the puzzle length n is even, the twists in the solution will not move the first-listed cubie.
Throws an Error if puzzleString is insane or unsolvable
(see isSane, isSolvable)
or if there are any bits set in whichToOrient
which are not also set in whichToPosition.
Currently also throws an Error if n > 3
(the solve algorithm is only implemented for n ≤ 3).
debugLevel specifies how much debugging output to send to System.out; this is probably not useful to the general public, unless you are curious to see how much thinking it's doing:
0 - none (default)
1 - print messages on entry/exit of top-level functions
2 - print messages on entry/exit of most functions
3 - print most function arguments and return values
4 - severe debug-- dump variables that I found useful at the time.
public static java.lang.String apply(java.lang.String movesString,
java.lang.String puzzleString)
movesString should be a spaces-separarated list of moves in the same form as that returned by solve()-- that is, each move consists of 3 letters, representing the color of the face being twisted, the from axis, and the to axis, respectively.
Each move may optionally be followed by a colon and a slicesMask, specifying which slices of the puzzle this twist should be applied to. For example, "abc:1" means the first slice (same as "abc"), "abc:2" means the second slice, "abc:5" means the first and third slice, "abc:-1" means all the slices regardless of puzzle size (i.e. a rotation of the entire puzzle at once).
Throws an Error if movesString does not represent
a valid sequence of moves or if puzzleString is insane
(see isSane).
It doesn't matter whether puzzleString
is solvable or not.
public static java.lang.String scramble(java.lang.String puzzleString,
int minScrambleChen,
int maxScrambleChen,
java.util.Random random,
int debugLevel)
apply).
To scramble a puzzle:
String scrambledPuzzleString = apply(scramble(puzzleString,
minScrambleChen,
maxScrambleChen,
random,
debugLevel),
puzzleString);
If the puzzle length n is even, the twists will not move the first-listed cubie.
Throws an Error if puzzleString is insane (see isSane)
or if not 0 ≤ minScrambleChen ≤ maxScrambleChen
or if d < 3.
NOTE: currently can return a sequence in which consecutive moves cancel each other. If you want to get more sophisticated, write your own scramble function :-)
public static java.lang.String readPuzzle(java.io.BufferedReader reader,
int debugLevel)
Implemented by reading and accumulating input lines from reader until the string is a valid puzzle string, and reading no further.
Throws an Error if end-of-file is reached without having seen a valid puzzle.
XXX Document debugLevel if I leave it in, otherwise provide XXX a way to access the functionality. XXX Should we throw an IOException (allowing that to be passed up?) XXX Should we throw some sort of exception on EOF instead of an error? XXX go over PuzzleIO.puzzleFromReader and make sure its behavior is suitable for public use
public static int n(java.lang.String puzzleString)
isSane).
public static int d(java.lang.String puzzleString)
isSane).
public static void main(java.lang.String[] args)
Has many command line options and interactive shell commands. For example, to scramble a 35 puzzle with 9 or 10 twists and then solve it:
java MagicCubeNdSolve 3 5 -scramble 9+ -solve
To load a puzzle from the beginning of the file MYPUZZLE.mcnd,
then apply two twists (the second of which
is an exotic middle-slice twist), and then solve:
java MagicCubeNdSolve -load MYPUZZLE.mcnd -exec ABc -exec cBa:2 -solve
There are many more options. To see a usage message,
run the program with no arguments.
Type "help" at the prompt to see the list of available
interactive commands.
public static void simple_main(java.lang.String[] args)
public static void trivial_main(java.lang.String[] args)
|
||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||