stannic
Member
kumi na tano 3.10 beta (Update 1)
Hello all.
I wrote a program capable to solve (MxN-1) sliding tile puzzles, such as the Fifteen puzzle. The program can solve puzzles from 2x2 to 11x11.
You can download the program by the following link:
Latest version (3.10 beta update 1, 10/05/2012): http://www.mediafire.com/?1sbq081n5ecv0ab
The program searches for suboptimal solutions like Kociemba's Cube Explorer. However, it can use more than two search phases. Additionally, the user can manually configure search phases.
The basic algorithm used in kumi na tano is multi-phase approach with slackness described on the Jaap's Puzzle Page. I've further generalized this algorithm to "multi-chained" version. The algorithm details are described in the manual, as well as usage of the program.
The program should run on Windows XP/Vista/7 x86/x64. There are two binaries knt32.exe and knt64.exe. Use one of them, depending on the OS installed.
For quick look at the program, click Wizard > Project Actions > Project > Open, then open project "sample" and click Activate button. When Solver tab becomes active, try scramble the puzzle using RND button and then click Search to find the solution.
I'll be glad to head any feedback about the program.
- stannic
Hello all.
I wrote a program capable to solve (MxN-1) sliding tile puzzles, such as the Fifteen puzzle. The program can solve puzzles from 2x2 to 11x11.
You can download the program by the following link:
Latest version (3.10 beta update 1, 10/05/2012): http://www.mediafire.com/?1sbq081n5ecv0ab
version 3.10 beta (Update 1) (10/05/2012): http://www.mediafire.com/?1sbq081n5ecv0ab
version 3.10 beta (10/04/2012): http://www.mediafire.com/?x5sjnoa3necoqjg
version 3.02 beta (9/29/2012): http://www.mediafire.com/?mmdyogbo6pqkdd2
version 3.01 (9/25/2012): http://www.mediafire.com/?17qnfshue7dgcpn
version 3.00 (9/24/2012): http://www.mediafire.com/?99dqxi7xi8nmh8c
- Batch solver reports the number of instances solved in exactly N moves
- Manual updated to the current version
- Manual updated to the current version
- Batch solver improved: information window (progress, current averages etc.); Save Report function (plain ASCII format)
- Added missing feature "Stop at slackness" (set to 1 to search only optimal solutions for each phase)
- Added antipodes for puzzles 2x2, 3x2, 4x2, 5x2, 6x2, 3x3, 4x3 in metrics 2TM, 3TM, 4TM
- Single click on ANP button will show the first antipode, and two small buttons will appear. Use these buttons to navigate between antipodes.
- Indicators "Parity error" and "Symmetric" in the Edit Instance window (Solver tab).
- Fixed bug with truncated text in message dialogs.
- Added missing feature "Stop at slackness" (set to 1 to search only optimal solutions for each phase)
- Added antipodes for puzzles 2x2, 3x2, 4x2, 5x2, 6x2, 3x3, 4x3 in metrics 2TM, 3TM, 4TM
- Single click on ANP button will show the first antipode, and two small buttons will appear. Use these buttons to navigate between antipodes.
- Indicators "Parity error" and "Symmetric" in the Edit Instance window (Solver tab).
- Fixed bug with truncated text in message dialogs.
- All found solutions are shown (longer solution does not disappear after shorter one is found).
- Bug fixed: Flip Rgn button should be disabled for non-square puzzles.
- Improved Create Project dialog: selecting both puzzle width and height by single click, accepting by double-click; additional information is in program hints.
- MD5-checksumming lookup tables to minimize risk of errors.
- Interface logic: STM and MTM aliases in filters on Regions tab changed back to 1TM and 10TM.
- Added two formats of the solution (Tile Compact and Blank Compact). See Options tab.
- Pop-up menu in the instance editor.
- Copy/paste instance (text format, blank square denoted by 0). Use CPY/PTE buttons or items in the popup menu.
- You can copy instance directly from takaken's solver.
- Batch solver improved (formerly Demo button).
- Antipodes and God's numbers for the following puzzles are hard-coded into the program:
STM metric: 2x2, 3x2, 4x2, 5x2, 6x2, 7x2, 8x2, 3x3, 4x3, 5x3, 4x4
MTM metric: 2x2, 3x2, 4x2, 5x2, 6x2, 3x3, 4x3, 4x4
- God's numbers are shown in the title and in hints in the Create Project dialog.
- Use ANP button to see antipodes (when available).
- Bug fixed: Flip Rgn button should be disabled for non-square puzzles.
- Improved Create Project dialog: selecting both puzzle width and height by single click, accepting by double-click; additional information is in program hints.
- MD5-checksumming lookup tables to minimize risk of errors.
- Interface logic: STM and MTM aliases in filters on Regions tab changed back to 1TM and 10TM.
- Added two formats of the solution (Tile Compact and Blank Compact). See Options tab.
- Pop-up menu in the instance editor.
- Copy/paste instance (text format, blank square denoted by 0). Use CPY/PTE buttons or items in the popup menu.
- You can copy instance directly from takaken's solver.
- Batch solver improved (formerly Demo button).
- Antipodes and God's numbers for the following puzzles are hard-coded into the program:
STM metric: 2x2, 3x2, 4x2, 5x2, 6x2, 7x2, 8x2, 3x3, 4x3, 5x3, 4x4
MTM metric: 2x2, 3x2, 4x2, 5x2, 6x2, 3x3, 4x3, 4x4
- God's numbers are shown in the title and in hints in the Create Project dialog.
- Use ANP button to see antipodes (when available).
- added aliases STM and MTM
- fixed bug with displaying length of the solution in various metrics
- updated manual
- fixed bug with displaying length of the solution in various metrics
- updated manual
Here are described some things that can be done with kumi na tano. For the full reference, please see the manual included in the archive (file manual.pdf or manual.rtf)
Wizard > Project Actions > Metric = MTM means that you have to switch to the Wizard tab (if you aren't already on it), find in the Project Actions window drop-down list Metric and set its value to MTM.
Also, for instance, Solver > Edit Instance > ANP denotes the small button ANP in the Edit Instance window on the Solver tab.
Also, for instance, Solver > Edit Instance > ANP denotes the small button ANP in the Edit Instance window on the Solver tab.
The following steps allow you to solve suboptimally any legal configuration of any MxN puzzle (M,N <= 11). Note, however, that the solution will be generally far from optimal. To find better solution, you may need to create project as described in the manual (page 26).
1. Run kumi na tano.
2. Click Wizard > Project Actions > Create button.
3. Set Box Width and Box Height to the width and height of the puzzle you want to solve.
4. Set Metric as you want.
STM is single-tile metric (only one tile per move); MTM is multi-tile metric (any number of tiles per move); 2TM, for example, is the metric that allows moving only 1 or 2 tiles per move (but not 3).
5. Check "Human "row-by-row" solving algorithm" checkbox.
6. Click OK button to close project creation dialog.
7. You will see the message asking if you want to activate the project. Click Activate button.
8. Wait until the activation is done. After activation, Solver tab will become active.
9. Click Solver > Edit Instance > RND button to scramble the puzzle.
10. Click Solver > Solver > Search to start search. The current best solution will display in the Solver > Solutions window.
11. Stop the solver at any time using Solver > Solver > Stop button when you decide that the solution is good enough.
12. Click Solver > Solutions > Play to view the solution in animation.
13. If you want to solve a particular configuration (not just random), check Solver > Edit Instance > D&S Mode checkbox.
14. Edit the configuration by dragging-and-dropping the tiles one onto another.
15. After editing is done, click Solver > Solver > Search button to solve the configuration.
1. Run kumi na tano.
2. Click Wizard > Project Actions > Create button.
3. Set Box Width and Box Height to the width and height of the puzzle you want to solve.
4. Set Metric as you want.
STM is single-tile metric (only one tile per move); MTM is multi-tile metric (any number of tiles per move); 2TM, for example, is the metric that allows moving only 1 or 2 tiles per move (but not 3).
5. Check "Human "row-by-row" solving algorithm" checkbox.
6. Click OK button to close project creation dialog.
7. You will see the message asking if you want to activate the project. Click Activate button.
8. Wait until the activation is done. After activation, Solver tab will become active.
9. Click Solver > Edit Instance > RND button to scramble the puzzle.
10. Click Solver > Solver > Search to start search. The current best solution will display in the Solver > Solutions window.
11. Stop the solver at any time using Solver > Solver > Stop button when you decide that the solution is good enough.
12. Click Solver > Solutions > Play to view the solution in animation.
13. If you want to solve a particular configuration (not just random), check Solver > Edit Instance > D&S Mode checkbox.
14. Edit the configuration by dragging-and-dropping the tiles one onto another.
15. After editing is done, click Solver > Solver > Search button to solve the configuration.
kumi na tano has an internal database containing God's numbers and antipodes for already solved puzzles. The following steps allow you to view all 17 STM antipodes (80-move positions) of the Fifteen Puzzle.
1. Run kumi na tano.
2. Click Wizard > Project Actions > Create button.
3. Set Box Width = 4 and Box Height = 4.
4. Set Metric = STM.
5. Uncheck "Human "row-by-row" solving algorithm" checkbox if it is checked.
6. Click OK button to close project creation dialog.
7. Manually switch to the Solver tab.
8. Click Solver > Edit Instance > ANP button. The first of 17 antipodes will be displayed in the Current Instance window.
9. Note that after clicking ANP button, two more small buttons appear on each side of the button. Use these buttons to view all antipodes one-by-one.
10. Click ANP button second time. You'll see the full list of antipode configurations.
11. Double-click on any line in the list to view the antipode.
1. Run kumi na tano.
2. Click Wizard > Project Actions > Create button.
3. Set Box Width = 4 and Box Height = 4.
4. Set Metric = STM.
5. Uncheck "Human "row-by-row" solving algorithm" checkbox if it is checked.
6. Click OK button to close project creation dialog.
7. Manually switch to the Solver tab.
8. Click Solver > Edit Instance > ANP button. The first of 17 antipodes will be displayed in the Current Instance window.
9. Note that after clicking ANP button, two more small buttons appear on each side of the button. Use these buttons to view all antipodes one-by-one.
10. Click ANP button second time. You'll see the full list of antipode configurations.
11. Double-click on any line in the list to view the antipode.
You can copy and paste the puzzle configuration from/to kumi na tano.
1. Create the simple project (Wizard > Project Actions > Create; Box Width = Box Height = 4; Metric = STM).
2 Right-click in the Solver > Current Instance window. The pop-up menu will display.
3. Click Copy to clipboard item to copy current puzzle configuration.
4. Paste it anywhere you want (e.g., in Notepad). It's simple text format.
5. Copy the following line to the clipboard:
1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 0
6. Right-click in the Current Instance window and select Paste from clipboard menu item.
7. You can use also buttons CPY and PTE in the Solver > Edit Instance window.
1. Create the simple project (Wizard > Project Actions > Create; Box Width = Box Height = 4; Metric = STM).
2 Right-click in the Solver > Current Instance window. The pop-up menu will display.
3. Click Copy to clipboard item to copy current puzzle configuration.
4. Paste it anywhere you want (e.g., in Notepad). It's simple text format.
5. Copy the following line to the clipboard:
1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 0
6. Right-click in the Current Instance window and select Paste from clipboard menu item.
7. You can use also buttons CPY and PTE in the Solver > Edit Instance window.
There are two common goal configurations used for MxN sliding tile puzzles:
You can set your preferred goal configuration from the Options tab.
Code:
Classic goal (Blank Last)
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x
Blank First goal
x 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
The basic algorithm used in kumi na tano is multi-phase approach with slackness described on the Jaap's Puzzle Page. I've further generalized this algorithm to "multi-chained" version. The algorithm details are described in the manual, as well as usage of the program.
The program should run on Windows XP/Vista/7 x86/x64. There are two binaries knt32.exe and knt64.exe. Use one of them, depending on the OS installed.
For quick look at the program, click Wizard > Project Actions > Project > Open, then open project "sample" and click Activate button. When Solver tab becomes active, try scramble the puzzle using RND button and then click Search to find the solution.
I'll be glad to head any feedback about the program.
- stannic
Last edited: