Peg solitaire solver (using depth-first search)

peg.py

#!/usr/bin/env python2.7

import sys

# Global constants
SIZE = 7
FINAL_BOARD = 1 << 24 # 1 << ((SIZE * SIZE - 1) / 2)

def solve(board):
    explored = set()
    position_moves = find_all_position_moves()
    return _solve(board, position_moves, explored)

def _solve(board, position_moves, explored):
    if board == FINAL_BOARD:
        return (board,)
    if board in explored:
        return ()
    for position, moves in enumerate(position_moves):
        for neighbor, target in moves:
            if is_valid_move(board, position, neighbor, target):
                next_board = move(board, position, neighbor, target)
                solution = _solve(next_board, position_moves, explored)
                if solution:
                    return (board,) + solution
    explored.add(board)
    return ()

def has_peg(board, position):
    return board & (1 << position) != 0

def is_valid_move(board, position, neighbor, target):
    valid_result = (1 << position) | (1 << neighbor) 
    mask = valid_result | (1 << target)
    return (board & mask) == valid_result

def move(board, position, neighbor, target):
    return board & ~(1 << position) & ~(1 << neighbor) | (1 << target)

def find_all_position_moves():
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    moves = [[] for i in xrange(SIZE * SIZE)]
    for i in xrange(SIZE):
        for j in xrange(SIZE):
            for dx, dy in directions:
                position = from_coords(j, i)
                if position is None: continue
                neighbor = from_coords(j + dx, i + dy)
                if neighbor is None: continue
                target = from_coords(j + 2 * dx, i + 2 * dy)
                if target is None: continue
                moves[position].append((neighbor, target))
    return tuple(moves)

def from_coords(x, y):
    in_range = (x >= 0 and x < SIZE) and (y >= 0 and y < SIZE)
    on_board = (x >= 2 and x < 5) or (y >= 2 and y < 5)
    return y * SIZE + x if in_range and on_board else None

def get_initial_board():
    full_board = 0
    for i in xrange(SIZE):
        for j in xrange(SIZE):
            position = from_coords(j, i)
            if position is not None:
                full_board = full_board | (1 << position)
    return full_board & ~FINAL_BOARD

def to_matrix(board):
    matrix = [None] * SIZE
    for i in xrange(SIZE):
        matrix[i] = [None] * SIZE
        for j in xrange(SIZE):
            position = from_coords(j, i)
            if position is not None:
                matrix[i][j] = 1 if has_peg(board, position) else 0
    return matrix

def to_string(matrix, peg='1', hole='0', off_board=' ', \
        col_delim=' ', row_delim='\n'):
    fmt = lambda value: off_board if value is None else [hole, peg][value]
    return row_delim.join(col_delim.join(map(fmt, row)) for row in matrix)

def main(program, *args):
    """ Main program """
    initial_board = get_initial_board()
    steps = solve(initial_board)
    for i, board in enumerate(steps):
        print '#%d' % i
        print to_string(to_matrix(board))
        print ''

# usage: python peg.py
if __name__ == '__main__':
    main(*sys.argv)