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:
From that initial state you should end up into this target state:
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:
- Am I already at the target state? If yes then Hurray!
- If no which means we have to take all available valid moves from current board state
- For each of the available board moves make move and recursively call Solve
- 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!