One of my earlier forays into solving a puzzle using Python was to solve the Rubiks cube. I, naively, thought it would be a simple matter to churn through all the available options until the program stumbled across the solution.
I made great progress with it... and then I started to research how difficult a task it really was. There were billions of solutions. Finally I realised Google had thrown their weight behind the puzzle, and determined the 'god' number. This is the minimum number of moves needed to solve a Rubiks cube from any position. It turns out the god number is 20.
At this point I put the Python solution for the Rubiks cube aside, at least temporarily. It turned out just learning how to actually do the Rubiks cube is much easier than you think! However, in the process, I had learnt a little about Breadth-first search and Depth-first search, and thought it would be great to solve a problem using one of these methods. More for my knowledge than anything else.
My son started to play with Pin Solitaire at a friends house one day, and I gave him a hand explaining the game. It's one of those things I have played with every so often, but never really tried to work out. This would be an ideal puzzle to solve using Python.
Surely it must be quite easy in comparison to the Rubiks cube!
To solve this problem, I used Depth-first search. It would be equally possible with Breadth-first search, it's just I was more interested in using the Depth-first search algorithm.
I am not going to go into great detail on Depth vs Breadth-first search. That may have to be basis of another blog post :-)
However Depth-first follows one potential solution until it finds a solution or reaches a dead end. At this point it then backtracks until there is another option available, which it follows to the end. So on and so forth until all options have been exhausted.
Breadth-first search would try out all the possible options available after just one move. It would then try out all the possible second moves, then the third moves etc. until the puzzle was solved.
If you are interested in researching a little more on this topic you can read more about both options here.
First of all I am going to show you my program in its entirety, and then take you through the programming of it line by line.
The first thing I do is allow the use of Python 3 print functions within Python 2. Something I have started to do more and more as I begin to think about making the transition from Python 2 to 3.
I also use the copy libraries, and the datetime libraries in my program so these are imported here.
If you recall the layout of a Pin Solitaire board, it's a 7 x 7 square with the 4 pins in each of the corners missing.
I have placed some Global Constants near the top of the program for a couple of reasons.
- It may be nice in the future to increase or decrease the size of the board. Who knows. Having the ability to make the modifications in one location in my program, which would affect the whole program, could be handy.
- When I want to use the Height or Width of the board in my program, using Height or Width makes the program so much more readable when I return to it in a few months time. Seeing the number 7 crop up in the code somewhere doesn’t mean much, and can be quite confusing. This will definitely make my code easier to read.
I always use capital letters with my constants.
The next are some variables which we will need to modify throughout the program.
Here is a quick explanation of each of these:
gameBoard = {} - I am going to store my board in a dictionary. This allows me to store the co-ordinates of each hole on the board alongside the information explaining if there is a peg or not at that location.
storeBoards = [] - I want to keep track of the moves I have made en route to a solution. This means that when I find a solution I have a list of all the moves I made to get there. If I reach a dead end, I will delete the move that took me there. This list of all the moves to reach a solution I will store in a list called storeBoards.
solutionCount = 0 - I want to keep track of the number of moves I have made in total. This will be updated every time I drill deeper into a solution. The only real purpose in keeping track of the number of moves I have made, is to allow me to check that progress is being made.
Now we get to the functions. These will make more sense if I explain them when we call them, rather than explain them all now.
So with that in mind, lets jump down to the main section of the program, after all the functions.
I want to log the time when I started solving the puzzle and when I finish. This will allow me to work out how long the puzzle took to solve.
So I store the current date and time in a variable called startTime. I will print that later, with endTime, when we have solved the puzzle.
I also want to save my solutions to a file. It's great showing the result on the screen, but once the puzzle is solved, I don’t want to have to keep running the solution again. So I will save the information in a text file called result.txt. This line creates and opens that file, so it is ready for data to be written to it.
Now onto the fun bit. I want to populate the blank dictionary I created earlier with a populated game of pin solitaire.
First of all let's populate it with a full version of solitaire. This means all holes are filled apart from the central one. The game most people recognise, and think of when they see pin solitaire.
I will call a function to populate the board, so I have
This is calling the function setupSolitaire(), and passing the empty dictionary, gameBoard, into it. gameBoard will be update from whatever is returned from this function.
Right lets leap into that function and see how that was written.
Directly under the Global Variables, you will see where I have written the function.
It starts off by defining the function and explains we are expecting a variable called board passed into it. Notice it doesn’t matter we are passing gameBoard into the function, but are referring to it as board within the function.
Now we have already said we will refer to each of the holes on the board as co-ordinates on a grid. Top left being 0,0 bottom right being 6,6.
This diagram explains what the co-ordinate system looks like.
This iterates through all the numbers from 0 to HEIGHT. We know HEIGHT is 7 so we will see the numbers 0,1,2,3,4,5,6. There is no number 7, but if you count them you will see there are 7 numbers.
We then iterate through all the numbers in the range WIDTH
This is a fairly common procedure of iterating through items such as co-ordinates.
Now we want to populate all positions on our board with a peg. Except the four pegs in each corner, oh and the central hole!
For a standard game we know that if the X co-ordinate falls in the first or last two columns AND the Y co-ordinates fall in the top or bottom two rows, then we will know that these should be blank, and not part of the game. This is what the next line states.
These lines use the constants we have declared at the start of our program. Using WIDTH, HEIGHT and CORNERSIZE to determine which co-ordinates should and should not be part of the board.
If they should not be part of the game, we make that co-ordinate in the dictionary associate with a space, ' '.
If it's not a corner piece, we then look for the middle piece, which we want to make a O, to indicate there is no peg in the hole.
Else, for all other positions, we assign an X, to indicate there is a peg in the hole.
Finally we want to pass the updated board back from our function, which we do so using
While researching the game a little more for the blog, I realised that there are many options for start games. While I am sure most people play the full version of pin solitaire, for test purposes, as will become clear later, its good to have some easier versions to solve.
So there are 6 alternative games you can run. These are currently commented out. However if you wanted to run one of these games then, you would comment out
And uncomment the game you want to solve.
To comment out a line, add a # in front of it, and delete the # if you want to uncomment a line.
So for each of the next six games, you need to create a function to set up the board as you like.
Once you know how to create one of these the others all follow the same pattern. Therefore I will explain just one to you, and let you read the code to see how the others work. Lets use the Cross as the example.
So the next line of code you see is
Which sends gameBoard to the function setupCross(), in much the same way as when we called the setupSolitaire() function.
We will write this function now.
Underneath the setupSolitaire() function you wrote earlier, create the function with
There are a number of ways to create the layout you need but the one I opted for was to call the setupSolitaire() function to fully populate the board, and then remove the pegs we no longer want. Lets call the function setupSolitaire() first of all.
You know by now this line populates the board fully, which we have just created.
The cross layout needs to look as follows
OOO
OXO
OOXXXOO
OOOXOOO
OOOXOOO
OOO
OOO
To do this we simply pick all the co-ordinates that need to change from being a X to a O.
To change the top left peg, we use the co-ordinate [2,0].
Where the 2 represents the X co-ordinate and the 0 the Y co-ordinate.
We know from earlier our co-ordinate system starts with [0,0] in the top left corner. Therefore in X, the first two co-ordinates are a space , ‘ ‘,. These need to stay the same so we don’t modify them.
We are simply changing items in our dictionary, from an 'X' to a 'O' for each co-ordinate that needs to change.
We have to go through all the other co-ordinates which require changing. This will look as follows:
The last change is actually putting a peg in the central position.
Finally we return our modified board.
We now have to go through a similar process for all the other starting shapes we need. We need to have a line of code to call the different starting positions, and a function to create each of them.
The different starting layouts are:
a plus
OOO
OXO
OOOXOOO
OXXXXXO
OOOXOOO
OXO
OOO
a fireplace
XXX
XXX
OOXXXOO
OOXOXOO
OOOOOOO
OOO
OOO
a pyramid
OOO
OXO
OOXXXOO
OXXXXXO
XXXXXXX
OOO
OOO
an arrow
OXO
XXX
OXXXXXO
OOOXOOO
OOOXOOO
XXX
XXX
and finally a diamond.
OXO
XXX
OXXXXXO
XXXXXXX
OXXXXXO
XXX
OXO
As I have shown you all the patters I don’t think I need to explain each of these to you in great detail!
Now we want to start to write the results to the text file we have created. Before we jump straight in and start writing the files, we should try to organise the file we create, otherwise it will not make sense when we open it at a later date.
First, we should show the board in the initial starting position. This will help us identify which problem we are solving. Let's write a line of text to the file, which explains what we are storing.
This line will write “Starting Board” to the file (outFile) we created earlier.
The \n part explains we want a new line in the file after Starting Board.
Now we call a function called printBoard, to print the board. If we simply printed the dictionary holding gameBoard we would get the whole contents of the dictionary, including the co-ordinates, and not the nice little print out of the board we are after.
Now go back to the top of your program and underneath all the functions to create the different start locations, you want to create the printBoard function.
First name the function and declare you are passing your board into the function.
If we were to simply print the gameboard, we would be printing the dictionary, and it would not look like a solitaire board.
If you remember from earlier we created a text file which we want to save the results to. Well that saving will happen in this function. I will also include the code to print the result to the screen at this point. My code has the code which prints to the screen commented out, so it is ignored by the program. However if I wanted to print the code to the screen, these lines can be un-commented to allow me to do so.
First we have to iterate through all the items in our dictionary.
We have already seen how we do this earlier in the program, when we were creating the standard layout of the board.
Now to print each item you would have the code.
This line prints what is stored in the dictionary for the co-ordinate [x,y]. I have added 'end = " "', as this stops a new line being printed after each item. Try with and without it later if you want to see the difference it makes. As I mentioned earlier I have commented out the code to print to the screen, but you can change this by uncommenting this line.
Now we want to write what is stored at the location [x,y] to our text file.
When we originally opened our text file we stored it as a variable outFile. This means if we want to do anything to our text file, we can do it to outFile.
The code to write to the file is as follows
The . after outFile shows we are treating outFile as an object. The syntax when working with an object is object.action.
So the object is outFile, and the action we want to do to this is writelines(). We want to write what is held in the dictionary at location [x,y] to the file. This is the same as what we wanted to print. Simply board[x,y].
Now once we have exhausted the end of all the items in the first row, we want to print the next row on a new line. To do this, at the same indentation level as the for y in range line, we add the following.
The print line, prints a new line. \n is the method used to indicate a new line. Again this is commented out, as I don't want to use it just now, but being able to uncomment the line if I want to print to the screen gives me the option to do that.
We also write a new line to outFile in much the same way.
Now when we have been through all the items, both in x and y, we will want to do the same thing.
Finally we return the function. I have stated we are returning None. You could just use return, but it makes it clearer I intended to return nothing from the function.
Now we have a function to print the board, lets go back to our main part of the function.
We see we are now calling a new function called listPossibleMoves, and passing our board into this, and the variable solutionCount which will store a count we will need as our program progresses.
This is the most crucial function in our program, which does the majority of the work.
Before we dive straight in let us think about this function.
We have already decided we will use Depth-first search. This uses something called a recursive function. A fancy name for saying a function which can call itself. It's quite easy to create a recursive function which keeps calling itself, over and over and over again. It would do this for ever. Therefore we have to structure our function properly, to stop this happening.
I am going to structure my function as follows:
If a solution has been found
return
else check all possible moves
if a move is possible make the move
Call the function again with the board layout which reflects the move
undo the move
That's a very brief overview of what we want our function to do. I have added in a few extra things in my code, to make it suit my needs a little more, but you will see those as we go along.
Before we dive into writing this function, I have separated the check to see if a solution has been found into a separate function. It is perhaps best to explain that function now, rather than in the middle of writing our listPossibleMoves() function.
So directly after our printBoard() function we will name our checkResult() function, and state we are passing into it a board, which is obvious, as we will need to supply it something to check.
So how do we know if the puzzle has been solved? Well... there would only be one peg left. So we can simply count the pegs. If there is more than one, then we have not succeeded, if there is one, the puzzle is solved. Pretty simple huh?The first thing we do is create something to keep track of our counting.
Now we check every item in the board.
If there is an X at that location we can increase the count.
To save time if the count gets above 1 we know we have not yet solved the puzzle, so we can return False
Otherwise, the count must be 1, it can never be less than 1, as there will always be one peg on the board. So we return True
So we can pass a board into this function, and if it is solved, it will return True, else it will return false.
Right so after that brief distraction, lets get back into writing the listPossibleMoves() function. Directly under our checkResult() function, we will declare listPossibleMoves.
So this line names our function as listPossibleMoves, and shows we are passing in the current version of our gameBoard into it, as well as the variable which is called solutionCount.
We now want to check if a solution has been found. Let's do this using the function we have just written called checkResult.
We know that checkResult returning True means we have solved the puzzle.
In our overview of this function, we said the next thing we would do is return. However before we do that, lets do a few other things.
We should write the solution to the file we have created. To make our file a little easier to read, we should write a text line that explains this is the start of a solution.
Remember \n creates a new line therefore \n\n creates two new lines.
Now we iterate through the list which is storing all the moves we have made so far. For each one, we will print that item, using our printBoard() function we wrote earlier. This will save the item passed into it to a file, and if we have uncommented the print statements, then it will also print the results to the screen.
Once all the moves to the solution have been made, we will write another line, which says we are at the end of the solution.
Finally we return from the function, as we said we would. We are returning solutionCount to ensure we keep this value up to date.
When planning this function out we said we would next check all possible moves. As the first part of the function was an 'if' statement, this part needs to be an 'else' statement.
So how do we check all possible moves? Well, we know that the pegs can only jump one of four ways. They can go up, down, left or right.
We know that we only want to attempt to move a peg, and not a hole.
We also know that a peg can only move if it jumps over another peg, into a hole.
Anything else? Well there is one other thing. If we are near the edge of the playing area, then we don't want to start looking beyond the playing area, as this will throw up an error. So we should bear this in mind.
Let us first of all check each of the positions on the board.
We want to now check each of the ways a peg at that position, if it is indeed a peg, can move. We will have to do these one at a time.
Lets start with the peg moving to the right. The next line looks quite complicated.
but it really isn't. We will break it own into smaller sections.
We mentioned earlier that we want to make sure that a move to the right stays within the bounds of the board we have created. We should only check pegs that are not within the nearest two columns of the right hand side. The right hand side is equal to our variable WIDTH, so we want to check pegs that are in a column less than WIDTH - 2.
Some of you may be asking should that not be less than WIDTH - 1? Well lets look at this is more detail.
If WIDTH = 7, this means we have 7 pegs. However these have an x co-ordinates of either a 0,1,2,3,4,5 or a 6.
WIDTH - 2 = 7 - 2 = 5.
Less than 5 are co-ordinates 0,1,2,3 or a 4.
As co-ordinate 4 is the 5th peg along, that can still make a jump to the right. If we used WIDTH - 1, that would leave us with co-ordinate 5, the 6th peg along. We would be checking if there is a peg two to the right of this, we would need a peg in co-ordinate 7, or the 8th peg along, which doesn't exist.
Hopefully that made sense!
We know that each item is defined by a co-ordinate system [x,y]. If we want to examine the x aspect of that we need to look in position 0 in the list. We can isolate this by saying item[0].
Therefore the first thing we want to check is
We also said we wanted to check if the item we are looking at is a peg. This would be an 'X'.
Now if we are moving a peg to the right, we need to check the spot two places to the right is a O, indicating a space.
To do that, lets check what is in that space.
By simply increasing the x co-ordinate of the item by 2 we can check if a O is in the position two places to the right.
Whats the last thing we need to check? That the item 1 place to our right is an X, as we have to jump over a peg.
gameBoard[item[0]+1,item[1]]=='X'
We can put all these individual elements together in one line, and using 'and' state they all need to be true.
So what do we have to do if all these things are true? Well we need to make the move. That entails jumping the peg two places to the right, and removing the peg we have jumped over.
So how do we change our board to match the fact that a peg has jumped over another peg.
Well the first thing is that the location where the peg was becomes empty.
Remember we are modifying our new copy of the board, and not the original board, as we will want to come back to that.
The next thing is the space we have jumped the peg into becomes a peg and not a space.
Finally the peg we have jumped over should be removed from the board.
Perfect.
As we have made a move, lets increase the count keeping track of the number of tries we have had at solving the puzzle.
When solving the puzzle, it is nice to ensure something is actually happening. Therefore every million (yes really) times we make a move, we should print something, so you know that the program has not crashed, and is still working.
solutionCount % 1000000 checks to see if there are any remainders when you divide solutionCount by 1000000. If there are no remainders, we know it is exactly divisible by 1000000, so we shall print the number. It's more for our sanity to check the program is running rather than aiding our program.
Now we do a check to see if we have already been to the new position. This is to stop us getting into a loop of returning to the same position again and again. However this is not necessary in our program, as there is no way to return to a previous state in Pin Solitaire as you are removing pins each move. However it would be necessary for solving other puzzles, such as the Rubiks cube, where you can return to a previous state. Therefore I have kept it in, as a reminder.
We now want to add the new position to our list which is keeping track of all the moves we have made. This will mean we have an up to date list of all the moves to reach a solution.
The next line is the most crucial line in Depth First Search. Have a read and see if you can notice what it does.
It calls the function we are already in, but with the Pin Solitaire board reflecting the move we have just made, and the solutionCount updated. The function is calling itself. This is known as a recursive function. We have made a move, and now we start drilling deeper into that move.
Imagine if we start to analyse the move we have just made, and realise there are no possible moves? We we will return from the function we have just jumped into, and we will want to check the other possible moves. Such as if the pin we are analysing tried to jump left or up or down, instead of right.
We will also want to remove the new position from the storeBoards, as that is no longer part of the solution we are analysing. Lets do that now.
As we have now returned to this function, after delving deeper into a solution we want to analyse what happens if we had jumped left or up or down instead.
Lets now examine the code below the comment
Well the code for jumping left is very similar to jumping right. However there are a few small differences. Instead of making sure we are two places from the right of the board, we need to be two places from the left. We also need to be looking to the left and not to the right, to see if the move is possible. Therefore the first line changes to look like
Everything else is the same!
So now we have checked the possibility of jumping right and left, we need to look to see what happens if we jump down.
Examine the code below.
In a similar way to ensuring we did not jump off the board when we jumped right, we need to do the same thing for down. Therefore we need to look at the Y co-ordinate and not the X co-ordinate, and check we are less than HEIGHT (not WIDTH) - 2
i.e. item[1] < (HEIGHT - 2)
When we decide to make the move, it is the Y co-ordinate we increase to modify the board to suit the move we have just made.
It is now easy to see what changes we need to make in the code following the
comment. I will let you look into those yourself.
So what happens if we have been through all the moves, and none are possible. Well we saw earlier that if the puzzle had been solved, and there was only one pin left we should return solutionCount which will allow us to in effect undo the last move we have made.
If we end up getting to a situation where there are no moves available, we should also return solutionCount and see what happened if we jumped the peg another direction.
There are two return statements in this function. The one which is part of the 'if' statement would return us up a level if a solution has been found. This first return statement will only happen if a solution has been found, which means the function will have called itself several times, and there is only one peg left. This second return statement, in the else part of the statement, could be called for similar reasons i.e. if it has reached the end of a branch, but not found any solution. This would mean eventually, once all possibilities have been checked, the program would return to the main part of the program.
If the program got this far it, and has exited all the recursive functions, then it would have finished its analysis of the board, and all possible moves. Any possible solutions will have been written to the result.txt file. Therefore we can now close the file.
We will also now make a note of the time when the program ended.
And finally, as we have stored both the start and the end times we can print them both, so help us determine the length of time the analysis took.
And that is the end of the program. All that is left to do is to run it. A word or warning though, if you are looking to solve the full puzzle, it really does take some time. So much so that I have not yet managed to leave a computer running long enough to prove a solution is found. I have however solved many of the other starting positions. The smaller ones take a matter of seconds to solve. So while it is quite a bit easier to solve than the Rubiks cube there is still a lot of processing to do on this.
For those of you interested in this, have a look at these web pages, which explain more about solving pin solitaire.
http://www.jaapsch.net/puzzles/solitaire.htm
http://www.durangobill.com/Peg33.html
http://home.comcast.net/~gibell/pegsolitaire/
I hope that you have found this tutorial interesting, and that it has introduced you to the notion of Depth First Search. Let me know if you use it to solve any interesting puzzles!
