Solving Peg Puzzles

Used backtracking and randomized approach - This doesn't really scale well. Takes long time for #pegs > 21. Working on improving it. Till then, beta version :)

## backtracking

## we start with following state of puzzle
##    + - Element present
##    0 - Hole is empty

##                 +
##             +       +
##         +       +       +
##     +       +       +       +
## +       +       0       +       +

## valid moves are from a point to next to next in same line removing the
## immediate next element. Go till there is only one element left

############ design - starts
##    1. every point is represented as a node and PuzzleState class is a
##    collection of such nodes
##    2. in each node, we can place a pebble or remove it
##    3. a notion of neighborhood is used to represent a collection of nodes
##    from which a node can be reached.
############ design - ends

import copy
import time
import random

class Node(object):
    " node class corresponding to a point"

    def __init__(self, name):
        self.element = True
        self.name = name      

    def removeElement(self):
        self.element = False

    def setElement(self):
        self.element = True

    def isEmpty(self):
        return not self.element

    def getName(self):
        return self.name

    def __eq__(self, right):
        return self.name == right.name

    def __str__(self):
        return (str(self.name) + \': Not Empty\'
            if self.element else str(self.name) + \': Empty\')

class PuzzleState(object):
    " state of the puzzle at any point of time "

    def __init__(self):
        self.nodes = []

    def __copy__(self):
        new = PuzzleState()
        new.nodes = self.nodes[:]
        return new

    def addNode(self, node):
        assert type(node) == Node
        self.nodes.append(node)

    def emptyNodes(self):
        return [x for x in self.nodes if x.isEmpty()]

    def setElement(self, node):
        assert type(node) == Node
        [x.setElement() for x in self.nodes if x == node]

    def removeElement(self, node):
        assert type(node) == Node
        [x.removeElement() for x in self.nodes if x == node]
                
    def noOfNodes(self):
        return len(self.nodes)

    def isEmpty(self, node):
        return any((x.isEmpty() for x in self.nodes if x == node))

    def __str__(self):
        return \'\\n\'.join(str(node) for node in self.nodes)

# a map of nodes to their neighbors
# 
"""
generates neighbors of the form 
node: [(via, neighbor_node), ...]

eg: neighbors = {
    "11": [("21", "31"), ("22", "33")],
    "21": [("31", "41"), ("32", "43")],
    ...
    }
"""
def generateNeighbors(length):
    neighbors = {}
    # generating downward neighbors
    for x in xrange(length-2):
        x = x+1
        f = x # from node
        p = 1 # start position
        while f > 0:
            k = 10*x+p
            neighbors[k] = [(10*(x+1)+p,10*(x+2)+p)]
            neighbors[k].append((10*(x+1)+p+1,10*(x+2)+p+2))
            p = p+1
            f = f-1
            
    # right ward neighbors
    for x in xrange(3, length+1):
        p = 1
        while True: # loop and a half
            k = 10*x+p
            if k in neighbors:
                neighbors[k].append((k+1, k+2))
            else:
                neighbors[k] = [(k+1, k+2)]
            p = p+1
            if p+2 > x: break
            
    # generating upward and leftward neighbors
    # this can be built out of the existing neighbors dictionary itself
    for node in neighbors.keys():
        for v,n in neighbors[node]:
            if n in neighbors:
                if (v,node) not in neighbors[n]:
                    neighbors[n].append((v,node))
            else:
                neighbors[n] = [(v,node)]
                
    # done !
    return neighbors

def buildPuzzle(length):
    "builds initial state of puzzle"
    puzzle = PuzzleState()
    for x in xrange(length):
        x = x+1
        r = x
        p = 1
        while x > 0:
            k = 10*r+p
            n = Node(k)
            puzzle.addNode(n)
            x = x-1
            p = p+1
    k = 10*length+((length/2)+1)
    puzzle.removeElement(Node(k))
    return puzzle

class SolvePuzzle(object):
    "solves a given puzzle state using back tracking"

    def __init__(self, length=5, verbose=False):
        self.neighbors = generateNeighbors(length)
        self.puzzle = buildPuzzle(length)
        self.verbose = verbose

        if verbose:
            import pprint
            print "Neighbors: "
            pprint.pprint(self.neighbors)
            print "Puzzle state: "
            print self.puzzle

    def solve(self, puzzle, moves=[]):

        if puzzle is None: puzzle = self.puzzle

        # we are done when all but one nodes are empty
        if puzzle.noOfNodes() - len(puzzle.emptyNodes()) == 1:
            print \'Done with all the movements !\'
            print \'Puzzle state: \'
            print puzzle
            print "Moves: "
            print moves
            return True
        
        # if we are in dead end, we return False
        if all((puzzle.isEmpty(Node(n)) or puzzle.isEmpty(Node(v))
                for x in puzzle.emptyNodes()
                if x.getName() in self.neighbors
                for v, n in self.neighbors[x.getName()])):
            if self.verbose: print \'Dead End !!\'
            if self.verbose: print puzzle
            return False

        # choose an empty node, one of its neighbors, make the movement and call
        # solve with new state puzzle
        empty = puzzle.emptyNodes()
        random.shuffle(empty)
        for node in empty:
            if node.getName() in self.neighbors:
                neighbors = self.neighbors[node.getName()]
                random.shuffle(neighbors)
                for v,n in neighbors:
                    if puzzle.isEmpty(Node(v)) or puzzle.isEmpty(Node(n)): continue
                    # we are making a movement here. let\'s copy puzzle object to avoid
                    # writing the original object and thus messin\' up backtracking
                    newPuzzle = copy.deepcopy(puzzle)
                    if self.verbose: print "Moving from ", n, " via ", v, " to ", node.getName()
                    newMoves = moves[:]
                    newMoves.append((n, node.getName()))
                    newPuzzle.removeElement(Node(n)) # from node
                    newPuzzle.removeElement(Node(v)) # middle node (which is actually removed)
                    newPuzzle.setElement(node) # to node

                    # sleep for a second before proceeding - for monitoring
                    # time.sleep(1)
                    
                    r = self.solve(newPuzzle, newMoves)
                    if self.verbose: print \'solve returned: \', r
                    if r: return True
                    
            else: continue

        # we have failed !
        if self.verbose: print "Searched exhaustively and failed !"
        return False

# unit tests
def tests():
    # Node class
    n = Node("A1")
    assert n.name == "A1"
    assert n.isEmpty() == False
    n.removeElement()
    assert n.isEmpty() == True
    t = Node("A1")
    assert n == t

    # PuzzleState class
    a = Node("A1")
    b = Node("A2")
    c = Node("A3")
    p = PuzzleState()
    p.addNode(a)
    p.addNode(b)
    p.addNode(c)
    p.removeElement(b)
    assert p.emptyNodes() == [b]
    assert p.isEmpty(b) == True
    p.setElement(b)
    assert p.isEmpty(b) == False

    # neighbors
    neighbors = generateNeighbors(5)
    assert set(neighbors[33]) == set([(22, 11), (43, 53), (32, 31), (44, 55)])
    assert set(neighbors[55]) == set([(54, 53), (44, 33)])
    assert set(neighbors[41]) == set([(31, 21), (42, 43)])

    print \'all tests passed !\'

# some unit tests
tests()

solver = SolvePuzzle(length=7, verbose=False) # verbose object
s = time.clock()
solver.solve(None) # start with solving initial state
print "Time taken: ", time.clock() - s