Skip to content

Instantly share code, notes, and snippets.

@hoheinzollern
Created January 4, 2012 12:02
Show Gist options
  • Save hoheinzollern/1559757 to your computer and use it in GitHub Desktop.
Save hoheinzollern/1559757 to your computer and use it in GitHub Desktop.
from copy import deepcopy
from pprint import pprint
board = [
[-1,-1, 1, 1, 1,-1,-1],
[-1,-1, 1, 1, 1,-1,-1],
[ 1, 1, 1, 1, 1, 1, 1],
[ 1, 1, 1, 0, 1, 1, 1],
[ 1, 1, 1, 1, 1, 1, 1],
[-1,-1, 1, 1, 1,-1,-1],
[-1,-1, 1, 1, 1,-1,-1]
]
(MOVE_LEFT, MOVE_RIGHT, MOVE_UP, MOVE_DOWN) = range(0,4)
move_str = ['left', 'right', 'up', 'down']
def moves(board):
'yields the possible moves for the given board'
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == 1:
if j >= 2 and board[i][j-1] == 1 and board[i][j-2] == 0:
yield ((i,j, MOVE_LEFT))
if j < len(board[i])-2 and board[i][j+1] == 1 and board[i][j+2] == 0:
yield ((i,j, MOVE_RIGHT))
if i >= 2 and board[i-1][j] == 1 and board[i-2][j] == 0:
yield ((i,j, MOVE_UP))
if i < len(board)-2 and board[i+1][j] == 1 and board[i+2][j] == 0:
yield ((i,j, MOVE_DOWN))
def apply_move(board, move):
'builds a new board with move applied'
(i, j, cmd) = move
board = deepcopy(board)
board[i][j] = 0
if cmd == MOVE_LEFT:
board[i][j-1] = 0
board[i][j-2] = 1
elif cmd == MOVE_RIGHT:
board[i][j+1] = 0
board[i][j+2] = 1
elif cmd == MOVE_UP:
board[i-1][j] = 0
board[i-2][j] = 1
elif cmd == MOVE_DOWN:
board[i+1][j] = 0
board[i+2][j] = 1
return board
def win(board):
'counts the pieces: if just one piece remains then the game is won'
count = 0
for line in board:
for item in line:
if item == 1:
count += 1
if count > 1:
return False
return True
def solve(board):
'solves the board: tries the possible moves until a win condition is found'
if win(board):
return (True, [])
for move in moves(board):
new_board = apply_move(board, move)
solved, steps = solve(new_board)
if solved:
return (True, [move] + steps)
return (False, [])
print "board:"
pprint(board)
solved, moves = solve(board)
if solved:
print "solved in %i steps:" % len(moves)
for i, j, move in moves:
print i, j, move_str[move]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment