A solver for marble solitaire game

marble-solitaire.py

import sys
import random


class Ball():
    directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

    def __init__(slf):
        # None = wall, False == free space, or another Ball instance
        slf.north = None
        slf.south = None
        slf.east = None
        slf.west = None
        slf.directions = []
        slf.position = ()


    def set_neighbours(slf, north, south, east, west):
        slf.north = north
        slf.south = south
        slf.east = east
        slf.west = west

    def get_neighbours(slf):
        # [(-1, 0), (1, 0), (0, 1), (0, -1)]
        return [slf.north, slf.south, slf.east, slf.west]

    def get_neighbour(slf, direction):
        if direction == (-1, 0):
            return slf.north
        elif direction == (1, 0):
            return slf.south
        elif direction == (0, 1): 
            return slf.east
        elif direction == (0, -1):
            return slf.west


    def can_jump(slf):
        slf.directions = []
        for i, ball in enumerate(slf.get_neighbours()):
            direction = Ball.directions[i]
            if ball and ball.__class__ == Ball:
                if ball.get_neighbour(direction) is False:
                    slf.directions.append(direction)
        if slf.directions: 
            return True

    def set_north(slf, i, j):
        if i == 0 or i == GRID_DIM:
            slf.north = None


# grid = [Ball() for i in range(2)]

# grid[0].set_neighbours(None, None, grid[1], None)
# grid[1].set_neighbours(True, None, None, grid[0])

GRID_DIM = 7
LBOUND = 2
HBOUND = 5

def make_grid():
    grid = [[None for i in range(GRID_DIM)] for j in range(GRID_DIM)] 
    for i in range(GRID_DIM):
        for j in range(GRID_DIM):
            if (LBOUND <= i < HBOUND) or (LBOUND <= j < HBOUND):
                ball = Ball()
                ball.position = (i, j)
                grid[i][j] = ball

    return update_grid(grid)

def update_grid(grid):
    for i in range(GRID_DIM):
        for j in range(GRID_DIM):
            ball = grid[i][j]
            if ball and ball.__class__ == Ball:
                ball.north = None if i == 0             else grid[i-1][j]
                ball.south = None if i == GRID_DIM - 1  else grid[i+1][j]
                ball.west  = None if j == 0             else grid[i][j-1]
                ball.east  = None if j == GRID_DIM - 1  else grid[i][j+1]
    return grid

def solved(grid):
    remaining_balls = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            ball = grid[i][j]
            remaining_balls += 1 if ball else 0
            if remaining_balls > 1:
                return False
    if remaining_balls:
        return True

def find_balls_that_can_jump(grid):
    balls_can_jump = []
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            ball = grid[i][j]
            if ball and ball.__class__ == Ball:
                if ball.can_jump():
                    balls_can_jump.append(ball)
    return balls_can_jump


def solve_grid(grid):
    balls_can_jump = find_balls_that_can_jump(grid)
    if not balls_can_jump:
        return solved(grid)
        
    for i, ball in enumerate(balls_can_jump):
        for j, direction in enumerate(ball.directions):
            new_grid = jump_ball(grid, ball, direction)
            # print_grid(grid)
            # if random.random() > 0.8: sys.exit()
            if solve_grid(new_grid):
                return new_grid
            print 'got here'

def jump_ball(grid, ball, direction):
    x, y = ball.position
    dx, dy = direction
    new_x, new_y = x + dx*2, y + dy*2

    # update new position of ball
    grid[new_x][new_y] = ball
    
    # remove jumped ball
    grid[x + dx][y + dy] = False

    # where ball where was is now empty
    grid[x][y] = False

    return update_grid(grid)

def start_game(grid):
    grid[3][3] = False
    grid = update_grid(grid)
    return grid

def print_grid(grid):
    balls = []
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            ball = grid[i][j]
            if ball and ball.__class__ == Ball:
                if ball.can_jump():
                    print '+',
                    balls.append(ball)
                else: 
                    print '-',
            elif ball is False:
                print '#',
            else:
                print ' ',
        print

    for ball in balls:
        print ball.position, ball.directions

grid = make_grid()
grid = start_game(grid)
print_grid(grid)
print_grid(solve_grid(grid))