M12

Overview

The following puzzle is inspired by the M12 puzzle that was mentioned in Scientific American. The object is to get the pieces in order. Press Flip to reverse the order. Press Merge to merge the pieces at the end of the puzzle with the ones at the beginning. Undo can undo moves. Random picks a random position. Reset returns to it's solved state.

More extensive documentation, including some explanation of it's inner workings, follow on this page. For right now just give it a try. Notice the bubble help for each button:

Trouble Shooting
If it does not work for you make sure you have Java 1.6 or later installed and that your browser is configured to display Java applets. In Firefox entering "about:plugins" in the URL field can be helpful in determining what version of Java your browser is using, if any. Also, if your monitor is much less than 1280 pixels wide then you'll have to scroll to the right to see the entire puzze. But it should work.

Puzzle Database
The status bar at the top, which is displayed in only in Cheat mode, indicates how far the puzzle is from solved. This is the main feature that distinguishes it from the Scientific American version - it has a built in database that indicates how many moves away a given board position is from solved. This is similar to way the Chess Endgame Databases work.

License

This puzzle is open source. It's covered by the GPL version 2 or later later. The source code is included in the applet's jar file, which can be downloaded here.

Buttons

• Flip - Reverses the order of the pieces. This is the same as "inverse" in the Scientific American version of this puzzle.
• Merge - Fold the puzzle onto itself so that the pieces at the end get merged into the pieces at the beginning. This is similar to the way a piece of taffy gets folded onto itself.
• Undo - Undoes the last move made.
• Random - Picks a random solvable position by doing 100 random moves.
• Reset - Restore the original solved position.
• About - Display the "About" message box.
• 1-5 - Only display pieces 1-5. This is helpful since it is only necessary to get pieces 1-5 in place to solve the puzzle. Pieces 6-12 are redundant.
• Black - Black pieces instead of colors. Might be helpful for low contrast monitors, or for people who don't like colors.
• Cheat - Cheat mode. The best move is highlighted in green. The status bar indicating how many moves the puzzle is from solved is displayed at the top.
• Easy - Switch to a much easier puzzle. This replaces flip and merge with swap and roll. Some of the other features, such as cheat, are disabled in easy mode since the database was generated for the original non-easy puzzle. Hint: If easy mode is still difficult for you then look into bubble sort.
• Letters - Letters instead of numbers. Whatever you prefer to look at.
• Record - Enter macro recording mode. To record a macro turn this option on, click a macro button, which should turn green. Make various moves and then finally click the macro button again. You should be asked a name for the macro. Turn record off when you are done creating macros in order to use them. Currently macros only record the Flip and Merge moves.
• Setup - Setup an arbitrary position. When enabled you can swap two pieces by first clicking the source piece, which will turn cyan, and then clicking the destination.
• Macro Buttons - When the Record option is enabled record a macro. When Record is not enabled play the macro back see the help for the Record button for details.

Technical
This section gives a brief overview over the technical innerworkings of
the puzzle.

Although this puzzle is a Java applet the same m12.jar file can be invoked on the command line. For example, to generate the database with filename ExampleM12.db try:

• java -jar m12.jar gen-db ExampleM12.db

To use the above generated database to solve a puzzle file named random.m12 using the database generated above:

• java -jar m12.jar load-db  ExampleM12.db solve random.m12

To display the GUI interface (same as the applet on this page):

• java -jar m12.jar gui 1

to generate and solve puzzles with a text interface. Invoking the puzzle in this way can also be used to generate the dbase/m12.db database. This isn't really documented. I can elaborate on using m12jar from the command line if anyone is interested.

The puzzle's database contains the number of moves away from solved every possible position is. So, in order to solve the puzzle (or to highlight the correct button in Cheat mode) the puzzle only needs to lookup the result of Flip and Merge in it's database. The move that gets it closer to solved (that reduces the number of moves away from being solved) is the correct move.

In order to reduce the size of the database at least two tricks are used First, the it makes use of the fact that it is only necessary to solve pieces 1-5. Pieces 6-12 then fall into place. Second, all possible positions of pieces 1-5 are tightly packed into the set of integers in the rage [0, 95040) where 95040 is 12! / 7!. That way each position only takes up a single byte in the database. The position is just the index into the database and the byte at that index is the number of moves away that position is from solved. See the code for details.