jumpypegthing

#Python 3.2
#Antti Virkkunen
#2014-03-12


import time

solution = []


class Board:
    pegs = []

    def __init__(self):
        self.pegs = [
                     [1],
                    [1,1],
                   [1,0,1],
                  [1,1,1,1],
                 [1,1,1,1,1]
                    ]

    def clone(self):
        newBoard = Board()
        newBoard.pegs = []
        i = 0
        for row in self.pegs:
            newBoard.pegs.append([])
            for peg in row:
                newBoard.pegs[i].append(peg)
            i+=1
        return newBoard

    def printPegs(self):
        offsetNumber = len(self.pegs[len(self.pegs) - 1]) - 1
        offsetString = " " * offsetNumber
        for subList in self.pegs:
            print(offsetString, end='')
            offsetString = offsetString[:-1]
            for peg in subList:
                print(str(peg) + ' ', end='')
            print()

    def sum(self):
        s = 0
        for row in self.pegs:
            for peg in row:
                s += peg
        return s

    def solve(self):
        if self.sum() == 1:
            solution.append(self)
            return True   #hooray we solved it!
        for i in range(0,len(self.pegs)):
            for j in range(0,len(self.pegs[i])):
                if self.pegs[i][j] == 1:
                    #up-left
                    if (
                    i >= 2
                    and j >= 2
                    and (self.pegs[i-1][j-1] == 1)
                    and (self.pegs[i-2][j-2] == 0)
                    ):
                        nextBoard = self.clone()
                        nextBoard.pegs[i][j] = 0
                        nextBoard.pegs[i-1][j-1] = 0
                        nextBoard.pegs[i-2][j-2] = 1
                        if nextBoard.solve():
                            solution.append(self)
                            return True
                    #up-right
                    if (
                    i >=  2
                    and j <= i-2
                    and (self.pegs[i-1][j] == 1)
                    and (self.pegs[i-2][j] == 0)
                    ):
                        nextBoard = self.clone()
                        nextBoard.pegs[i][j] = 0
                        nextBoard.pegs[i-1][j] = 0
                        nextBoard.pegs[i-2][j] = 1
                        if nextBoard.solve():
                            solution.append(self)
                            return True
                    #down-left
                    if (
                    i+2 < len(self.pegs)
                    and (self.pegs[i+1][j] == 1)
                    and (self.pegs[i+2][j] == 0)
                    ):
                        nextBoard = self.clone()
                        nextBoard.pegs[i][j] = 0
                        nextBoard.pegs[i+1][j] = 0
                        nextBoard.pegs[i+2][j] = 1
                        if nextBoard.solve():
                            solution.append(self)
                            return True
                    #down-right
                    if (
                    i+2 < len(self.pegs)
                    and (self.pegs[i+1][j+1] == 1)
                    and (self.pegs[i+2][j+2] == 0)
                    ):
                        nextBoard = self.clone()
                        nextBoard.pegs[i][j] = 0
                        nextBoard.pegs[i+1][j+1] = 0
                        nextBoard.pegs[i+2][j+2] = 1
                        if nextBoard.solve():
                            solution.append(self)
                            return True
                    #left
                    if (
                    j >= 2
                    and (self.pegs[i][j-1] == 1)
                    and (self.pegs[i][j-2] == 0)
                    ):
                        nextBoard = self.clone()
                        nextBoard.pegs[i][j] = 0
                        nextBoard.pegs[i][j-1] = 0
                        nextBoard.pegs[i][j-2] = 1
                        if nextBoard.solve():
                            solution.append(self)
                            return True
                    #right
                    if (
                    j+2 < len(self.pegs[i])
                    and (self.pegs[i][j+1] == 1)
                    and (self.pegs[i][j+2] == 0)
                    ):
                        nextBoard = self.clone()
                        nextBoard.pegs[i][j] = 0
                        nextBoard.pegs[i][j+1] = 0
                        nextBoard.pegs[i][j+2] = 1
                        if nextBoard.solve():
                            solution.append(self)
                            return True

        return False


def main():
    board = Board()
    board.printPegs()
    print("pegs: " + str(board.sum()))
    if board.solve():
        print("Solvable")
        solution.reverse()
        print("-------------")
        for board in solution:
            board.printPegs()
            print()
    else:
        print("Unsolvable")

startTime = time.time()
main()
print(str(time.time() - startTime) + " seconds")