The Power of Habit - Book Review

The Power of Habit, written by Charles Duhigg, a New York Times reporter is both a fascinating and informative book. Duhigg takes a trip into the human mind and helps explain why we do what we do. Throughout the book Duhingg backs up his ideas with interesting anecdotes both about experiments conducted to research individuals habits, and experiences people have been through. All of this is written in an easy to read manner, which ensures the pages keep turning.

While the whole book touches on habits, it examines them into three distinct sections.

Part 1 - The habit of individuals
Part 2 - The habits of successful organisations
Part 3 - The habits of societies.

There is a very small section on the end which is a readers guide to using these ideas.

While these three sections are very much linked through looking at habits, each one could stand alone in its own right. Looking at these three distinct areas really makes you appreciate the power of being able to tap into habits. 

Part 1 of the book deals with why people have habits, and how the brain ensures you a carry out certain activities almost subconsciously. The three aspects of habits are discussed.

Cue —> Routine —> Reward

It certainly makes you more self aware about why you do certain things, and what you can do to change.

Part 2 then jumps into examining organisations, which was absolutely fascinating. From how an American Football coach went on to win the Super Bowl by changing players habits, to how Starbucks became a world leader. How a crisis can bring a company together, to how supermarkets know what you want to buy before you do! Quite wide ranging topics, but all linked with how scientific, and once you realise, how obvious habits are.

Finally in Part 3, Duhigg looks into how societies can change through habit. Duhigg uses the powerful anecdote of Rosa Parks, and how a small incident transformed a nation. In this section we also look at societies views on peoples habits, which touches on the moral and legal aspects of Habits.

When dealing with each of thee topics, whether explaining the science, or the history of what happened, Duhigg gets the level of detail right. You certainly don’t feel bogged down in the science, or too involved in the minute details of the history.

If I had to level any criticism at the book it would be that I felt the first part of the book was a little repetitive. While the final section on how readers should implement these ideas came across as a little bit of an after thought, and may have been better implemented in Part 1. However this should not put you off reading the book, but if you do find the book a little slow at first, it is absolutely worth persevering, as it matures as you progress.

Don’t be fooled into thinking this book is only for those who would like to stop biting their nails. When laid out in front of you, from so many perspectives you become aware that your habits control your life more than you realise. Even if you don’t have any habits that you want to manipulate, after reading this book, you will become aware your habits are already being manipulated by others, without your consent.

The Checklist Manifesto - Book Review

When I was handed the checklist manifesto and told it is a fascinating book about the power of checklists, I was somewhat sceptical. A book about checklists? Everyone knows about checklists, don't they? A few boxes to tick when things are done. But how on earth does anyone write a whole book about them? I was curious.

Within minutes of starting the book, I was hooked.

The author Atul Gawande is a general and endocrine surgeon, who also runs the World Health Organisations Safe Surgery Saves Lives Program. The book takes you through Gawandes quest to find a method of improving healthcare and saving lives. While it focusses heavily on the authors experience in the medical world, it absolutely is not a book written for the medical profession.

Gawande takes a peek into other industries, and how they have solved hugely complex problems. Flying planes which experienced test pilots have crashed, building skyscrapers, finance, even operating a top restaurant. The secret to success? The humble checklist. Gawande states we have more knowledge than we ever have had, but the volume and complexity of what we know has exceeded our individual ability to deliver its benefits correctly. The secret to success? The humble checklist.

Through his research of other industries and his own implementation of a checklist for the World Health Organisation Gawande shows some statistics demonstrating the power of checklists. These are simply staggering, to the point that when Gawande first saw the results of a checklist he had implemented, he could not believe them.

So why are checklists not implemented in more places? The book covers the fallacies of humans, and how they think a humble checklist is beneath them. For anyone who has tried to implement a new system in the work place, they will recognise the resistance seen by Gawande while trying to get others to adopt his method. Many people believe that a simple checklist is beneath them. However stories such as the pilots and crew of the plane which landed in the Hudson River in Manhattan soon remind you of their power. Was this ‘miracle’ down to the pilots skill; or the pilots checklist?

So while this book is about the humble checklist, and the vast benefits they can reap, it’s about so much more. Ticking boxes is not the ultimate goal. It’s about encouraging a culture of teamwork. It’s about recognising even the smartest, highly trained people can make mistakes. It’s about looking outside your world and learning from other industries. It’s about empowering staff. It’s about becoming more efficient.

Gawande has written an easy to read engaging book with a powerful message. I found it so compelling that when I reached the end, I turned straight back to page one and read it again. It is that good. I would encourage you all, even if you feel a checklist is beneath you, to follow the checklist I have created below.


Read this book.
Read it again.

Turn Your Raspberry Pi into a Twitterbot

Ok. So this was a post I had decided I was not going to write. The reason for this is I did not want to help people create something negative, such as a spam generator.

Then I had a quick look at the Wikipedia page about Twitterbots. I realised there are some really fantastic ideas out there for Twitterbots, which can have a positive impact.

So I decided to go ahead and write the blog post, and to trust people to use it the right way. :-)

Besides, one of the the Twitterbots I have written is testing the Infinite Monkey Theorem to simulate a monkey trying to type the complete works of Shakespeare. The monkey automatically tweets his progress (@TheMonkeyBard).

So who am I to judge? :-)

In this blog post I am going to show you how I wrote another Twitterbot, which sends out a tweet, from a list of pre-written tweets, at a certain time. For me I use it to automatically post my blogs to twitter at certain times of the day. To disguise the fact I am doing this, I have added a slight element of randomness in there, so it doesn't look too much like a Twitterbot. More on that later.

To start with here is the code in its entirety. Have a read through it and see if it makes sense to you, we will then run through this line by line.

from __future__ import print_function #Allows python3 use of print()
import random
import string
import tweepy
import os

FILEPATH = '/home/pi/Desktop/TwitterBot' 

# Consumer keys and access tokens, used for OAuth 
consumer_key =  'YourConsumerKey' 
consumer_secret = 'YourConsumerSecret'
access_token = 'YourAccessToken' 
access_token_secret =  'YourAccessTokenSecret'

# OAuth process, using the keys and tokens
auth = tweepy.OAuthHandler(consumer_key, consumer_secret)
auth.set_access_token(access_token, access_token_secret)

# Creation of the actual interface, using authentication
api = tweepy.API(auth)


## This function sends the tweets. It will check the length of them first of all.      
def sendTweet(tweetText):
    randomNumber = random.randrange(4) #number 0 - (randrange-1) use 4
    #print (randomNumber) #Use for debugging
    if randomNumber == 0:
        api.update_status(status=tweetText) 
        #print (tweetText) #Use for debugging
        return None
    else:
        return None 
        
## This function will print one of the random Tweets
def randomTweet():
    try:
        tweetFile = open(os.path.join(FILEPATH,'Tweets.txt'),'r')
        tweetList = tweetFile.readlines()
        tweetFile.close()
        randomChoice = random.randrange(len(tweetList))
        #print (tweetList[randomChoice]) #For debugging only
        sendTweet(tweetList[randomChoice])
        return None
    except IOError:
        return None        
 
randomTweet()

Now in order to get started with this you will need to do two things.

1. Install Tweepy.
2. Create an app on Twitter

I am not going to explain either of these processes, as I learned how to do this from another blog by the wonderful Raspi.tv. They have done a far better job than I could ever do on this, so please go and read this blog on setting up Tweepy, and then come back to me. :-)

The link you need to follow is here:

http://raspi.tv/2013/how-to-create-a-twitter-app-on-the-raspberry-pi-with-python-tweepy-part-1#app

Right, you are back? Good!

So the first lines of code call in some libraries including Tweepy, which should now be installed on your Raspberry Pi.

from __future__ import print_function #Allows python3 use of print()
import random
import string
import tweepy
import os

The first line allows us to use the Python 3 version of print, which is something I am trying to do a little more these days. The next 4 lines all call libraries we need to use.

The next line caused me the most problems. When you run your program using cron (more on this later), your program needs to know exactly where to go looking for any files you call. Normally I would be in the current directory when I run this program, so this line would not matter. When you run your program using cron it is starting from a different directory, so this line is necessary.

If you don't know what cron is don't worry, it's not difficult. I will explain all later.

FILEPATH = '/home/pi/Desktop/TwitterBot' 

The path to my directory is /home/pi/Desktop/TwitterBot, but you will have to modify this line to suit your requirements.

So how do you find out the location of your program? Well, you can navigate to it in the command line, and then type:

pwd

This will return the directory of where your files are. In my case I store them on the desktop in a folder called TwitterBot. We will use this information later in our program.

So you read the blog post by Raspi.tv? You should therefore have been able to set up an app in twitter, and be able to fill out the information required in these lines of code.

# Consumer keys and access tokens, used for OAuth 
consumer_key =  'YourConsumerKey' 
consumer_secret = 'YourConsumerSecret'
access_token = 'YourAccessToken' 
access_token_secret =  'YourAccessTokenSecret'

# OAuth process, using the keys and tokens
auth = tweepy.OAuthHandler(consumer_key, consumer_secret)
auth.set_access_token(access_token, access_token_secret)

# Creation of the actual interface, using authentication
api = tweepy.API(auth)

Ensure you replace the text in the first 4 lines with your consumer key, consumer secret, access token and access token secret. For your reference, if you just want a reminder of where to find all the information, you need to go to the twitter apps website.

https://apps.twitter.com/

That's all the difficult twitter stuff out of the way. There are just two functions we need to write. One chooses a random tweet, and one tweets it.

Let us look at the function which sends the tweets.

## This function sends the tweets. It will check the length of them first of all.      
def sendTweet(tweetText):
    randomNumber = random.randrange(4) #number 0 - (randrange-1) use 4
    #print (randomNumber) #Use for debugging
    if randomNumber == 0:
        api.update_status(status=tweetText) 
        #print (tweetText) #Use for debugging
        return None
    else:
        return None 

The first line

def sendTweet(tweetText):

creates the function, but also expects some text, stored in a variable called tweetText, to be passed into it. It is the text in tweetText that we will be tweeting.

So this function does two things. It sends the tweet, which is what you would expect, but not every time... I have added an element of randomness into this so it only tweets once in every four attempts. Why did I do this? Well I wanted to post tweets at four times during the day - Midnight, 6am, lunchtime and 6pm, using GMT.  But I don't want to send a tweet every time. I think one tweet a day, on average, is enough to advertise my blog post. So if I use cron to potentially post four times a day, but reduce the chance of posting to one time in four, on average I will post once a day, but at one of the four pre-determined times. Hope that makes sense!

I did this to make it look a little less like a Twitterbot, which would normally post the same time every day. It just mixes it up a little and means there is a chance for a reader from other time zones to see one of my posts.

So that's what the first line does, it picks a random number from 0 to 3, and stores it in the variable randomNumber. You can increase or decrease the frequency by playing around with the number in random.randrange().

    randomNumber = random.randrange(4)

I then use an if statement to check if that number is == 0, which in our program will be once in every four attempts on average.

    if randomNumber == 0:

If it is we then send a tweet made up of the text we passed to our function, which is stored in tweetText. This makes use of the Twitter API to send the tweet.

        api.update_status(status=tweetText) 

We then return from the function.

        return None

If randomNumber is not equal to zero, the program will just return without doing anything.

    else:
        return None

All very simple so far.

The second function we need to write is randomTweet(). This chooses one of the random tweets to send to the sendTweet() function. The tweets it will be choosing from are stored in a text file called Tweets.txt.

## This function will print one of the random Tweets
def randomTweet():
    try:
        tweetFile = open(os.path.join(FILEPATH,'Tweets.txt'),'r')
        tweetList = tweetFile.readlines()
        tweetFile.close()
        randomChoice = random.randrange(len(tweetList))
        #print (tweetList[randomChoice]) #For debugging only
        sendTweet(tweetList[randomChoice])
        return None
    except IOError:
        return None  

We start off by naming the function. As you will see from the empty brackets this function is not expecting anything to be passed into it.

def randomTweet():

We are going to use Try and Except in this function. I do this in case there is an error loading up the file as I don't want the program to crash if it cannot find the file it is trying to open.

    try:
        tweetFile = open(os.path.join(FILEPATH,'Tweets.txt'),'r')
        tweetList = tweetFile.readlines()
        tweetFile.close()

So we Try the following.

We open the file Tweets.txt and store the contents in the variable tweetFile. But as I mentioned earlier when we come to run cron, we need to give the full path to this file. So we use this command

(os.path.join(FILEPATH,'Tweets.txt')

to join Tweets.txt onto the filepath stored in FILEPATH. The reason I have stored the filepath in FILEPATH, is if I want to change it in the future, I only have to modify it in one place. That place is at the top of the program, so easy to find!

We then store the contents of tweetFile into tweetList using readlines. This separates the text into a list which stores each line as a different item in the list.

     tweetList = tweetFile.readlines()

Finally we close the open text file.

     tweetFile.close()

We then analyse the length of our list, and pick a random number from 0 to the length of the list. The result is stored in randomChoice.

        randomChoice = random.randrange(len(tweetList))

And then we send the item which is in that random location in the list to the function we wrote earlier called sendTweet.

        sendTweet(tweetList[randomChoice])

Then we return None

        return None

Finally if there was an error in our try part of the function we catch it and just return from the function doing nothing.

    except IOError:
        return None  

Ok so far so good? Anything missing?

Well if we don't call a function in our program then nothing will run. So we just call the function randomTweet() to kick things off the ground.

randomTweet()

And that is that, the programming is complete.  There really is nothing tricky in all of this.

But if you want this program to tweet we are not quite finished. There are two things remaining. You need to create a text file called Tweets.txt and store this in the same folder as your program. This text file should have each tweet you want to send on a different line in the text file, as shown below.

Tweet 1
Tweet 2
Tweet 3
Tweet 4
Tweet 5

Finally while we have our python program completed, and our Tweets.txt file created, we need some method of telling our Raspberry Pi to run it when we want it to be run.

This is where the wonderful tool called cron comes into its own.

In the past I have written a blog post explaining how cron works. Definitely worth a read. But if you just want to get on and get your Twitterbot underway then I will explain what you need to do.

I said earlier that I would like my Twitterbot to (potentially) tweet 4 times a day. I say potentially as there is randomness in the the code to ensure it only tweets one in four times. To tell the Raspberry Pi to try to tweet at four times in the day I will have to add four lines of code to my crontab file.

On your Raspberry Pi you need to open a terminal window and type

Crontab -e

This will open up the file you need to modify, probably using a text editor called nano.

You will need to enter the following text at the bottom of this:

00 00 * * * /usr/bin/python /home/pi/Desktop/TwitterBot/TwitterBot.py 
00 06 * * * /usr/bin/python /home/pi/Desktop/TwitterBot/TwitterBot.py 
00 12 * * * /usr/bin/python /home/pi/Desktop/TwitterBot/TwitterBot.py 
00 18 * * * /usr/bin/python /home/pi/Desktop/TwitterBot/TwitterBot.py

A brief explanation of each of these lines is as follows:

• For each of the lines the first 00 refers to the minutes past the hour we want our program to run. 
• 00,06,12,18 refer to the hour, (24 hour format) at which we want the program to run. 
• * * * refer to day of Month, Month and Day of week respectively. We want to ignore all these, so use a * for each.  
• The /usr/bin/python explains you want to launch your program with python. 
• /home/pi/Desktop/TwitterBot/TwitterBot.py gives the full path to the program you want to run. 

Press ctrl-x and follow the instructions to save and exit.

And that is that. You have a fully functioning Twitterbot which will try to tweet 4 times a day, but on average will only manage it once :-)

I hope this has given you the basics of turning your Raspberry Pi into a Twitterbot. Let me know what Twitterbots you create!

Turn your Raspberry Pi into an Audiophile Music Player

So my younger brother came to stay recently and asked me to give him a hand to do something with his Raspberry Pi. Always eager to help out with all things Raspberry Pi related, I had a look into what he wanted to do.

He told me he wanted to set up Volumio. I have to admit I had never heard of Volumio, but by the time we were finished setting it up, I was sold! It is very cool! What's more it was so easy to set up! Almost too easy to warrant a blog post...

However - where is the fun in that?

So what is Volumio? Well Volumio calls itself a Linux Audiophile Music Player. Basically it turns your Raspberry Pi, or many other devices, into a Music Player. You can simply add a USB stick with your music on it, and Volumio will play it. The great thing is you control the music remotely, so don't need anything other than a speaker/headphones connected to your Raspberry Pi.

So first of all you will need to download Volumio. Go to their website, and click on Download.

https://volumio.org/project/

Once the download is completed you need to flash it onto a suitable SD Card. I am assuming that you already know how to do this, but if not, there are instructions on the Volumio web site on how to do this using either Linux, MacOSX or Windows. It's the same method as you would load any Linux distribution onto a SD Card.

For the purposes of trying this out, I am using a 4GB card. However Volumio is fairly small so has no problem fitting on a card that size.

Once that is done put the newly created SD card into your Raspberry Pi and fire it up! At this point you will need to have your Raspberry Pi connected to your router via an ethernet cable. We will sort out going wireless later.

Open an internet browser on your computer, and go to the following link:

http://volumio.local/

Your screen should look something like this. 

How easy was that? 

However there is no point having an Audiophile Music Player without any music to play.

The next thing you need to do is to put some music onto a USB stick, and insert this into your Raspberry Pi. You might notice the bottom left of the screen indicates it is Updating. This takes a few minutes depending on how many songs you have on the USB stick.

Once completed this will resort back to saying Browse.

Plug your Headphones / Speaker into the Headphone Port of your Raspberry Pi. On older Raspberry Pi's this is the blue port, or on a Raspberry Pi 2 the port next to the HDMI port.

Now click on Browse and then on USB, and then follow your filing system on your USB stick until you find the song you want to play and double click on it.

Here I chose the Cantina Band from the Star Wars album. A message will appear saying you have added it to the playlist. It should start playing immediately.

Selecting other songs will add them to the play list also. Click on Playlist at the bottom to view the Playlist you have created.



The Playback menu allows you to see what is playing and change the volume etc.



It really is so simple and intuitive to use!

Want to listen to internet radio? Instead of clicking on USB, you can click on Web Radio. There are a number of pre-defined radio stations.




Earlier I mentioned that you can set this up so it works over WiFi. I use an Edimax EW-7811UN Dongle, but I have also tested this with a Wi-Pi dongle and they both work equally well. You can pick these up cheaply on the internet.

To set this up click on Menu and then Network.

Type in your Network Name, for me this is Spongebob (Don't judge me - ok?), the type of security you have, along with your password.

Finally click on Save Changes. They may take a few minutes to save. However once finished you should see your Edimax Blue LED Light up.

You can now remove your network cable, and be connected wirelessly.

And there you have it, your Raspberry Pi is a fully functioning Jukebox!

Take Volumio a step further and download an app, so you can control your music selections using your phone or tablet. Enjoy!

Solving Peg Solitaire using Depth First Search in Python

I am a huge fan of puzzles, and think that my love of programming comes from that enjoyment. There is something hugely satisfying about finding the solution to a puzzle.

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.

Depth First Search (DFS)

Breadth First Search (BFS)

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.

from __future__ import print_function #Allows python3 use of print()
import copy
import datetime

##Global Constants
WIDTH = 7
HEIGHT = 7
CORNERSIZE = 2

##Global Variables
gameBoard = {}
storeBoards = []
solutionCount = 0

## Functions

#Setup Fully Populated Board
def setupSolitaire(board):
    for y in range (HEIGHT):
        for x in range (WIDTH):
            if ((x in range(0,CORNERSIZE) or x in range(WIDTH-CORNERSIZE,WIDTH))
             and (y in range(0,CORNERSIZE) or y in range(HEIGHT-CORNERSIZE,HEIGHT))):
                board[x,y] = ' '
            elif x == (WIDTH/2) and y == (HEIGHT/2):
                board[x,y] = 'O'
            else: 
                board[x,y] = 'X'
    return board
    
def setupCross(board):
    board = setupSolitaire(board)
    board[2,0] = 'O'
    board[3,0] = 'O'
    board[4,0] = 'O'
    board[2,1] = 'O'
    board[4,1] = 'O'
    board[0,2] = 'O'
    board[1,2] = 'O'
    board[5,2] = 'O'
    board[6,2] = 'O'
    board[0,3] = 'O'
    board[1,3] = 'O'
    board[2,3] = 'O'
    board[4,3] = 'O'
    board[5,3] = 'O'
    board[6,3] = 'O'
    board[0,4] = 'O'
    board[1,4] = 'O'
    board[2,4] = 'O'
    board[4,4] = 'O'
    board[5,4] = 'O'
    board[6,4] = 'O'
    board[2,5] = 'O'
    board[3,5] = 'O'
    board[4,5] = 'O'
    board[2,6] = 'O'
    board[3,6] = 'O'
    board[4,6] = 'O'
    board[3,3] = 'X'
    
    return board
    
def setupPlus(board):
    board = setupSolitaire(board)
    board[2,0] = 'O'
    board[3,0] = 'O'
    board[4,0] = 'O'
    board[2,1] = 'O'
    board[4,1] = 'O'
    board[0,2] = 'O'
    board[1,2] = 'O'
    board[2,2] = 'O'
    board[4,2] = 'O'
    board[5,2] = 'O'
    board[6,2] = 'O'
    board[0,3] = 'O'
    board[6,3] = 'O'
    board[0,4] = 'O'
    board[1,4] = 'O'
    board[2,4] = 'O'
    board[4,4] = 'O'
    board[5,4] = 'O'
    board[6,4] = 'O'
    board[2,5] = 'O'
    board[4,5] = 'O'
    board[2,6] = 'O'
    board[3,6] = 'O'
    board[4,6] = 'O'
    board[3,3] = 'X'
    
    return board
    
def setupFireplace(board):
    board = setupSolitaire(board)
    board[0,2] = 'O'
    board[1,2] = 'O'
    board[5,2] = 'O'
    board[6,2] = 'O'
    board[0,3] = 'O'
    board[1,3] = 'O'
    board[3,3] = 'O'
    board[5,3] = 'O'
    board[6,3] = 'O'
    board[0,4] = 'O'
    board[1,4] = 'O'
    board[2,4] = 'O'
    board[3,4] = 'O'
    board[4,4] = 'O'
    board[5,4] = 'O'
    board[6,4] = 'O'
    board[2,5] = 'O'
    board[3,5] = 'O'
    board[4,5] = 'O'
    board[2,6] = 'O'
    board[3,6] = 'O'
    board[4,6] = 'O'


    return board    

def setupPyramid(board):
    board = setupSolitaire(board)
    board[2,0] = 'O'
    board[3,0] = 'O'
    board[4,0] = 'O'
    board[2,1] = 'O'
    board[4,1] = 'O'
    board[0,2] = 'O'
    board[1,2] = 'O'
    board[5,2] = 'O'
    board[6,2] = 'O'
    board[0,3] = 'O'
    board[6,3] = 'O'
    board[2,5] = 'O'
    board[3,5] = 'O'
    board[4,5] = 'O'
    board[2,6] = 'O'
    board[3,6] = 'O'
    board[4,6] = 'O'
    board[3,3] = 'X'
    
    return board

def setupArrow(board):
    board = setupSolitaire(board)
    board[2,0] = 'O'
    board[4,0] = 'O'
    board[0,2] = 'O'
    board[6,2] = 'O'
    board[0,3] = 'O'
    board[1,3] = 'O'
    board[2,3] = 'O'
    board[4,3] = 'O'
    board[5,3] = 'O'
    board[6,3] = 'O'
    board[0,4] = 'O'
    board[1,4] = 'O'
    board[2,4] = 'O'
    board[4,4] = 'O'
    board[5,4] = 'O'
    board[6,4] = 'O'
    board[3,3] = 'X'
    
    return board
    
def setupDiamond(board):
    board = setupSolitaire(board)
    board[2,0] = 'O'
    board[4,0] = 'O'
    board[0,2] = 'O'
    board[6,2] = 'O'
    board[0,4] = 'O'
    board[6,4] = 'O' 
    board[2,6] = 'O'
    board[4,6] = 'O'
    board[3,3] = 'X'
    
    return board
    

def printBoard(board):
    for y in range (HEIGHT):
        for x in range (WIDTH):
            #print (board[x,y], end = " ") #The end prevents new lines being printed 
            outFile.writelines(board[x,y])   
        #print ('\n')
        outFile.writelines('\n')
    #print ('\n')
    outFile.writelines('\n')
    return None
    
def checkResult(board):
    count = 0
    for item in board:
     if board[item] == 'X':
         count += 1 
            if count >1:
             return False
    else:# The count must be 1
        return True 

def listPossibleMoves(gameBoard,solutionCount):

    if checkResult(gameBoard) == True:
        outFile.writelines('Start Solution\n\n')
        for item in storeBoards:
         printBoard(item)
         
        outFile.writelines('End Solution\n\n')
        return solutionCount
        
    else:        
        for item in gameBoard:
            ##Check if piece can move in + X
            if item[0] < (WIDTH - 2) and gameBoard[item]=='X' and gameBoard[item[0]+2,item[1]]=='O' and gameBoard[item[0]+1,item[1]]=='X':
                new = copy.deepcopy(gameBoard)
                new[item] = 'O'
                new[item[0]+2,item[1]]='X'
                new[item[0]+1,item[1]]='O'
                solutionCount += 1
                if (solutionCount % 1000000) == 0:
                 print (solutionCount,'solutionCount')
                if new not in storeBoards:
                    storeBoards.append(new)
                    solutionCount = listPossibleMoves(new,solutionCount)
                    storeBoards.remove(new)
             
            
            ##Check if piece can move in - X
            if item[0] > (1) and gameBoard[item]=='X' and gameBoard[item[0]-2,item[1]]=='O' and gameBoard[item[0]-1,item[1]]=='X':
                new = copy.deepcopy(gameBoard)
                new[item] = 'O'
                new[item[0]-2,item[1]]='X'
                new[item[0]-1,item[1]]='O'
                solutionCount += 1
                if (solutionCount % 1000000) == 0:
                 print (solutionCount,'solutionCount')
                if new not in storeBoards:
                    storeBoards.append(new)
                    solutionCount = listPossibleMoves(new,solutionCount)
                    storeBoards.remove(new)     
         
             ##Check if piece can move in + Y
            if item[1] < (HEIGHT - 2) and gameBoard[item]=='X' and gameBoard[item[0],item[1]+2]=='O' and gameBoard[item[0],item[1]+1]=='X':
                new = copy.deepcopy(gameBoard)   
                new[item] = 'O'
                new[item[0],item[1]+2]='X'
                new[item[0],item[1]+1]='O'
                solutionCount += 1
                if (solutionCount % 1000000) == 0:
                 print (solutionCount,'solutionCount')
                if new not in storeBoards:
                    storeBoards.append(new)
                    solutionCount = listPossibleMoves(new,solutionCount)
                    storeBoards.remove(new)

                
             ##Check if piece can move in - Y
            if item[1] > (1) and gameBoard[item]=='X' and gameBoard[item[0],item[1]-2]=='O' and gameBoard[item[0],item[1]-1]=='X':
                new = copy.deepcopy(gameBoard)
                new[item] = 'O'
                new[item[0],item[1]-2]='X'
                new[item[0],item[1]-1]='O'
                solutionCount += 1
                if (solutionCount % 1000000) == 0:
                 print (solutionCount,'solutionCount')
                if new not in storeBoards:
                    storeBoards.append(new)
                    solutionCount = listPossibleMoves(new,solutionCount)
                    storeBoards.remove(new)

        return solutionCount
        
startTime = datetime.datetime.now()
outFile = open ('result.txt','w') 

#gameBoard = setupSolitaire(gameBoard)
gameBoard = setupCross(gameBoard)
#gameBoard = setupPlus(gameBoard)
#gameBoard = setupFireplace(gameBoard)
#gameBoard = setupPyramid(gameBoard)
#gameBoard = setupArrow(gameBoard)
#gameBoard = setupDiamond(gameBoard)

outFile.writelines('Starting Board\n')

printBoard (gameBoard)

listPossibleMoves(gameBoard,solutionCount)

outFile.close()
endTime = datetime.datetime.now()

print ('Starttime = ', startTime)
print ('EndTime = ', endTime)

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.

from __future__ import print_function #Allows python3 use of print()

I also use the copy libraries, and the datetime libraries in my program so these are imported here.

import copy
import datetime

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.

##Global Constants
WIDTH = 7
HEIGHT = 7
CORNERSIZE = 2

I always use capital letters with my constants.

The next are some variables which we will need to modify throughout the program.

##Global Variables
gameBoard = {}
storeBoards = []
solutionCount = 0

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.

startTime = datetime.datetime.now()

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.

outFile = open ('result.txt','w') 

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

gameBoard = setupSolitaire(gameBoard)

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.

#Setup Fully Populated Board
def setupSolitaire(board):

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.

We start by saying

    for y in range (HEIGHT):

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

       for x in 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.

           if ((x in range(0,CORNERSIZE) or x in range(WIDTH-CORNERSIZE,WIDTH))
             and (y in range(0,CORNERSIZE) or y in range(HEIGHT-CORNERSIZE,HEIGHT))):

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, ' '.

                board[x,y] = ' '

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.

            elif x == (WIDTH/2) and y == (HEIGHT/2):
                board[x,y] = 'O'

Else, for all other positions, we assign an X, to indicate there is a peg in the hole.

            else: 
                board[x,y] = 'X'

Finally we want to pass the updated board back from our function, which we do so using

    return board

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

gameBoard = setupSolitaire(gameBoard)

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

gameBoard = setupCross(gameBoard)

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

def setupCross(board):

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.

    board = setupSolitaire(board)

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].

    board[2,0] = 'O'

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:

    board[3,0] = 'O'
    board[4,0] = 'O'
    board[2,1] = 'O'
    board[4,1] = 'O'
    board[0,2] = 'O'
    board[1,2] = 'O'
    board[5,2] = 'O'
    board[6,2] = 'O'
    board[0,3] = 'O'
    board[1,3] = 'O'
    board[2,3] = 'O'
    board[4,3] = 'O'
    board[5,3] = 'O'
    board[6,3] = 'O'
    board[0,4] = 'O'
    board[1,4] = 'O'
    board[2,4] = 'O'
    board[4,4] = 'O'
    board[5,4] = 'O'
    board[6,4] = 'O'
    board[2,5] = 'O'
    board[3,5] = 'O'
    board[4,5] = 'O'
    board[2,6] = 'O'
    board[3,6] = 'O'
    board[4,6] = 'O'

The last change is actually putting a peg in the central position.

    board[3,3] = 'X'

Finally we return our modified board.

       return 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.

outFile.writelines('Starting Board\n')

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.

printBoard (gameBoard)

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.

def printBoard(board):

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.

    for y in range (HEIGHT):
        for x in range (WIDTH):

     
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.

            #print (board[x,y], end = " ") #The end prevents new lines being printed 

         
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

            outFile.writelines(board[x,y]) 

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.

        #print ('\n')
        outFile.writelines('\n') 

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.

    #print ('\n')
    outFile.writelines('\n')

 
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.

  return None

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.

listPossibleMoves(gameBoard,solutionCount)

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.

def checkResult(board):

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.

    count = 0

 
Now we check every item in the board.

    for item in board:

 
If there is an X at that location we can increase the count.

     if board[item] == 'X':
         count += 1 

     
To save time if the count gets above 1 we know we have not yet solved the puzzle, so we can return False

            if count >1:
             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

    else:# The count must be 1
        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.

def listPossibleMoves(gameBoard,solutionCount):

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.

    if checkResult(gameBoard) == True:

 
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.

        outFile.writelines('Start Solution\n\n')

     
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.

        for item in storeBoards:
         printBoard(item)

       
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.

        outFile.writelines('End Solution\n\n')

Finally we return from the function, as we said we would. We are returning solutionCount to ensure we keep this value up to date.

        return solutionCount

 
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.

    else: 

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.

        for item in gameBoard:

     
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.

            if item[0] < (WIDTH - 2) and gameBoard[item]=='X' and gameBoard[item[0]+2,item[1]]=='O' and gameBoard[item[0]+1,item[1]]=='X':

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

if item[0] < (WIDTH - 2)

 We also said we wanted to check if the item we are looking at is a peg. This would be an 'X'.

gameBoard[item]=='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.

gameBoard[item[0]+2,item[1]]=='O'

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.

            if item[0] < (WIDTH - 2) and gameBoard[item]=='X' and gameBoard[item[0]+2,item[1]]=='O' and gameBoard[item[0]+1,item[1]]=='X':

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.

Easy. Or maybe not. We need to copy the game-board first of all, so then we can always come back to the board if the path we take to solve the puzzle doesn't work out. We have to do a deepcopy, otherwise when the copy of the board changes, the original will change also.

                new = copy.deepcopy(gameBoard)

             
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.

                new[item] = 'O'

             
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.

                new[item[0]+2,item[1]]='X'

             
Finally the peg we have jumped over should be removed from the board.

                new[item[0]+1,item[1]]='O'

             
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.

                solutionCount += 1

             
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.

                if (solutionCount % 1000000) == 0:
                 print (solutionCount,'solutionCount')

               
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.

                if new not in storeBoards:

             
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.

                    storeBoards.append(new)

                 
The next line is the most crucial line in Depth First Search. Have a read and see if you can notice what it does.

                    solutionCount = listPossibleMoves(new,solutionCount)

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.

                    storeBoards.remove(new)

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

            ##Check if piece can move in - X

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

            if item[0] > (1) and gameBoard[item]=='X' and gameBoard[item[0]-2,item[1]]=='O' and gameBoard[item[0]-1,item[1]]=='X':

If we decide to make the move, we need to modify the pins to the left of the pin we are looking at.

                new[item[0]-2,item[1]]='X'
                new[item[0]-1,item[1]]='O'

             
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.

             ##Check if piece can move in + Y

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)

            if item[1] < (HEIGHT - 2) and gameBoard[item]=='X' and gameBoard[item[0],item[1]+2]=='O' and gameBoard[item[0],item[1]+1]=='X':

You will see that the X part of the co-ordinate is staying the same, but we are checking what the state of the board is in the positions if we were to move down, by looking what happens if we increase the Y part of the co-ordinate.

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

             ##Check if piece can move in - Y

           
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.

        return solutionCount

     
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.

 outFile.close()

We will also now make a note of the time when the program ended.

endTime = datetime.datetime.now()

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.

print ('Starttime = ', startTime)
print ('EndTime = ', endTime)

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!