chinese_checkers.py

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]