Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement