Solving My Pocket Solitaire using Top-Down method

This post continues My Pocket Solitaire series.

This time we’re starting to open up the solving logic for this puzzle. Playing of the game starts from the initial position:

No canvas support so cannot display the board :-( Sorry!

From that initial state you should end up into this target state:

No canvas support so cannot display the board :-( Sorry!

In order to achieve that you have to make series of valid moves where you jump over piece with another piece into empty space and then you remove the piece which got “jumped over” (read more from here).

Now we have actually defined all the necessary definitions what we need in order to proceed further:

• Initial state
• Valid move
• Target state

And us human beings tend to solve these kind of puzzles using “top-down” thinking. It’s easiest way to start but at the same time it’s extremely inefficient. But before we’ll talk more about the efficiency part let’s take a look at Pseudocode about this top-down solving logic:

 Solve 
  Validate board state
  If board is at the target state
    Hurray!
  Else
    Get list of valid moves for current state
    For each move in valid moves list
      Make move
   Recursively call Solve
      Undo move

Program
  Initialize board to initial state
  Call Solve

You can see that this Algorithm is very simple and into some extend it even models “human thinking” (but when humans tend to get stuck they go back to the initial state instead of recovering to the previous state). Pseudo program starts from the line 12 and it first initializes board to initial state and then it calls recursive method called Solve. Solve follows simple logic:

1. Am I already at the target state? If yes then Hurray!
2. If no which means we have to take all available valid moves from current board state
3. For each of the available board moves make move and recursively call Solve
4. When call returns back then undo previous move (recover to state where we still had options)

This logic is easy to read and easy to implement. So if you’re just starting programming I think this is good exercise to get you started with algorithms .

However as I mentioned it’s inefficient. So how *bad* is the performance of this then? Well simple diagram demonstrates it pretty well (click image to see it larger):

X-axis of the diagram is tree level in solution. Meaning level 1 indicates initial state where there are 4 valid moves available (in another words 4 subtrees from that given position). Level 2 already has 12 subtrees etc. You can better see this from this table:

Y-axis of the diagram is count of subtrees in logarithmic scale. So it’s pretty easy to understand from the diagram that count of subtrees pretty much explodes. It just means that if you use this “top-down” method when solving this (or similar logical problems) you’ll end up into poor performance IF your target is to maximize the solving performance.

Quite often when I talk about this kind of logical problems with someone I get these kind of comments (or very similar): “Just add some parallel execution to it and it’s way faster then”. Well I don’t think that you should use horse power to solve problems if you’re using completely wrong algorithm . First you implement better algorithm (and I prefer to do it with single thread approach since it has many advantages and maybe I’ll come back to this in the future posts) and then you can think how to leverage available horse power from the machine(s). But remember that horse power doesn’t ever fix bad algorithm.

And if you would like to know how many unique solutions there are in this board game then you wouldn’t get answer to your question when implemented using this method. In future posts we’ll cover that topic too.

Anyways... Happy hacking!

J