knights.py

#!/usr/bin/env python
#-*- coding:utf-8 -*-
from pprint import pprint
import itertools
import sys
import psyco
psyco.full() # Makes things about 30% - 40% faster

def display(board):
    """ Prints a human-readable representation of the board to the screen """
    for row in board:
        for cell in row:
            if cell == 0:
                print "  ◦",
            else:
                print "%3d" % cell,
        print ""

def valid_move(board, r, c):
    """ Returns 'true' if the move is inside the board and is empty (equal to 0) """
    return min(r,c) >= 0 and max(r,c) < 8 and board[r][c] == 0

def possible_moves(board, r, c):
    """ Returns a list of possible squares the knight could go to. """
    deltas = (
                (-2,-1),
                (-2,1),
                (2, -1),
                (2, 1),
                (1,2),
                (1,-2),
                (-1,2),
                (-1,-2)
            )
    return ((guess[0] + r, guess[1] + c) for guess in deltas
            if valid_move(board, guess[0] + r, guess[1] + c))

def ordered_possible_moves(board, r, c):
    """ Returns a list of possible squares the knight could go to
    using Warnsdorff's algorithm- for each possibility, see how many
    possible moves could be taken from there, then order it by the smallest. """
    
    moves = possible_moves(board, r, c)
    move_degree = [len(possible_moves(board, nr, nc)) for nr,nc in moves]
    return [move for _, move in sorted(zip(move_degree, moves))]

    
count = 0
def consider(board, position, move_depth):
    """ Given a board, a position where the knight is, and how many moves
    before, this will recursively consider all the possible boards that could be
    made until it finds one that's solved. """
    global count
    count += 1
    if count % 10000 == 0:
        sys.stdout.write(".")
        sys.stdout.flush()
    if count == 1000000:
        # Considering the 65th move. That means all 64 moves are filled. That
        # means the board is solved.
        print "\nHit: %d moves." % count
        display(board)
        # Returning true stops the whole sequence. This means only one
        # solution will be found.
        return True
    for move in possible_moves(board, *position):
        # For this move, create a copy of it. Then, fill in the right square.
        # Then, print it.
        r,c = move
        board[r][c] = move_depth
        if consider(board, move, move_depth + 1):
            # We found something, so stop right here
            return True
        # That didn't work. Reset our move.
        board[r][c] = 0
        

initial = [[0 for x in xrange(8)] for x in xrange(8)] # board[row][column]
# Board full of 0s

start = (1,4) # Where the knight goes first
initial[start[0]][start[1]] = 1
# Put the first move here

print "Initial:"
display(initial)

consider(initial, start, 2) # Start considering the second move