front page

Sliding Pentominos

 

Search

Search is an algorithm that tries to solve the puzzle. It is a exhaustive approach that looks for a move in minimum steps only. (08-2003 -- That has now changed). If the number of steps is too great your computer will run out of memory -- and that's easy to do! There are ways to improve the algorithm, and I may try these some day, but some problems will always be too big for a PC. The more space on the tray that is not used by the board, the more difficult it is for a computer solution (the 9x10 tray is particularly hard -- my pc runs out of memory and it has 1 Gb of it!). In these cases humans can do much better!

A compounding problem is that even if your PC has lots of memory, the browser's Java interpreter seems to limit itself to around 66 Mbytes. I don't know of a way around this for browsers. Using Sun's Webstart technology it is now possible to use as much memory as your PC has. You will have to set the memory on the page (there is a button to do that) before calling the webstart version.

Search will print the steps it is taking. If your PC starts to run slow, you can regain control by pressing "Abort" and stopping the search.

If Search finds a solution, it places it in the History, and you can follow the moves by pressing the ">>" button. So before using Search, it's a good idea to "Home" the board to 0 steps.

If a solution in minimum steps is known, the number of steps is printed above the board. If a solution was done by hand, or using an algorithm that does not guarantee a minimum length, that number is followed by '?'. If "impossible" is printed then it has been determined that for this shape and size of the tray, there is no solution. For example, if Search reports that is has exhausted the search, then a solution is impossible.

Some of the following may not be available from the applet version.

Traceback

Menu: Preferences -> Search -> Traceback solution
To save memory. the traceback can be disabled. This means a solution may be traced, but Search won't remember how to get back to the main board. So we can tell a solution exists, but we can't tell what it is! Some of the minimal steps were determined this way.

Search From Both Ends

Menu: Preferences -> Search -> Search from both ends
There is a new version of Search (08-02-2003). By default now the search is started from both ends: the main board and the target board. In some cases this is faster and requires less memory -- but not always. And it does not always produce a least steps solution.
Some examples:

Board Memory
Single Search Direction Search From Both Ends
Fallen Sumo I, A -> B 10 Steps 10 Steps, 65Mb 10 Steps, 14Mb
Fallen Sumo II, A -> B 18 Steps 18 steps, 193Mb 18 steps, 74Mb
Three Stooges, 8x10 Tray, A -> B 30 Steps 30 Steps, 123Mb 31 Steps, 214Mb
Three Stooges, 9x10 Tray, A -> B 6 Steps 6 Steps, 350Mb 6 Steps, 17Mb

Show Sample Boards During Search

This option is on by default. It doesn't seem to cost much and makes for a livelier display.

Beam Width

This is experimental. Lowering the search beam width means ignoring board configurations that are too complex. The result is fewer states examined, so if a solution is found it is unlikely to be in minimum steps unless it is also found at large beam. Nevertheless, lowering the beam does reveal solutions in many cases where memory simply runs out at high beam.