Knights Tour - Auto-Solver, written in Python

What follows is my first attempt at a Knights Tour solver.

It is written in Python (2.6), and is currently pretty ugly, but it works.
I'll post updates as I add them (IF I add them). Feel free to comment.

Steve

 

#-------------------------------------------------------------------------------
# Name:        Knights Tour - Autosolver Three
# Version:     3.3 (Board visuals improved and code tidied and expanded)
# Purpose:
#
# Author:      Steve
#
# Created:     26/11/2010
# Copyright:   (c) Steve 2010
# Licence:     Beerware - if you like it, buy me a beer
#-------------------------------------------------------------------------------
#!/usr/bin/env python
 
from time import sleep, time
import sys
import os
 
 
# Semi-intelligent brute force with backtracking.  Move until blocked, then back 
# up and try again (DFS).  Select next move based on proximity to edge.
# ONLY checks for a complete tour - open or closed.  
 
# TODO: enable directional searching (ie: if possible, move only clockwise)
 
# TODO: Continue the complete tree of possible tours and return each, and show
# whether or not it is open or closed.
 
# TODO: Apparently some people like to test non-sqare boards - convert boardSize
# to bsx and bsy so rectangular boards can be tested. (I will ignore knights tour
# extremists who have irregular shaped boards as well, that just seems pointless.
 
# TODO: improve the lame 'best guess' options in the getBestMove() function
# Needs massive code-base tidy-up
 
# TODO: Magic tours - testing? http://www.maa.org/mathland/mathtrek_10_06_03.html
 
# These are global variables - not very Pythonic, but they work for now
numberOfTours = 1     # How many tours to find (to be implemented)
tours = []            # Store each tour for later reference
closed = 0            # Store the number of closed tours found
boardSize = 6         # The number of squares on each side
knight = (0, 0)       # (y, x) location of Knight at beginning
moves = []            # The stack for storing explored nodes (board positions)
visited = 0           # The marker for the list position
board = [["" for i in range (boardSize)] for i in range (boardSize)] # Empty board
sleepTime = (1.0/(boardSize**2)) # Faster (smaller delay) for larger boards
 
# Note: The stack configuration is as follows:
# a list of lists, each inner (sub-) list starts with the first position and is 
# followed by all possible moves from that point.  Each location is a (y,x) tuple.
# ie: [[(0,0),(2,1)],[(1,2),(...
 
def main():
    global knight, board, numberOfTours # ...or Python chokes
 
    # Place knight in initial position, initialisation
    moveKnight(knight)                # Place knight in initial location
    possibleMoves = getMoves(knight)  # Then get all initial moves
    for itr in possibleMoves:         # Finally, add them to the moves list
        moves[0].append(itr)
    #printBoard()
 
    # Now start the main process of intelligent brute force
    while numberOfTours > 0: # Have we completed the prerequisite number of tours?
        pos = len(moves)-1           # Get the index of the last sub-list
        if len(moves[pos]) > 1:      # Check if this pos has any available moves
            knight = getBestMove(pos)# If it does, get the best possible move
            moveKnight(knight)       # And move there
            #printBoard()             # Then print the board so we can see the move
            possibleMoves = getMoves(knight) # Get all possible moves from the new pos
            for itr in possibleMoves:
                moves[pos+1].append(itr)   # Then add each to the current sub-list pos
            #print 'The current stack is', moves # Debugging print
 
        else: # There are no possible moves from this position (either complete, or blocked)
            if len(moves) >= boardSize**2: # To get here, we must have completed a tour.
                numberOfTours -= 1         # So reduce the counter and tidy up
                tours.append([i[0] for i in moves]) # append this tour sequence
                printBoard()               # Print the completed tour
                print tours[-1]             # print the tours sequence
                firstMove = moves[0][0]    # Now check if this tour was closed or not
                lastMove  = moves[-1][0]
                if (abs(firstMove[0] - lastMove[0]) == 2 and abs (firstMove[1] - lastMove[1]) == 1) or \
                   (abs(firstMove[0] - lastMove[0]) == 1 and abs (firstMove[1] - lastMove[1]) == 2):
                    print "Closed Tour!"
                    tours[-1].append('Closed')
                backtrack(knight) # Tour complete, do the next one
            else: 
                backtrack(knight) # Backtrack one place and try again    
    return
 
 
 
def getBestMove(pos):
    global moves
    # TODO: simplify this by ranking all moves in order based on a value calculated
    # based on its proximity to the border (ie: (0,1) would be 1 and (0,0) would be 0
    # (2,1) would be 2.  Similarly (5,5) on a 6x6 board would be 0 since its on the
    # boundary at the other side.
    # Question: Should ALL corners (or any corners) be higher priority?
    # ie: Should (1,1) be more valuable than (1,2) or (2,1)?
    #
    # 0 1 1 1 1 1 0 Example board position values
    # 1 2 2 2 2 2 1
    # 1 2 3 3 3 2 1
    # 1 2 3 4 3 2 1
    # 1 2 3 3 3 2 1
    # 1 2 2 2 2 2 1
    # 0 1 1 1 1 1 0
 
    # Currently this does NOT scale... its good for small boards ie: 5x5
    # Dirty scan for super-best moves
    for i in range(1, len(moves[pos])): # Start at pos 1 to avoid evaluating the key location
        p = moves[pos][i]
        if p[0] == p[1] == 0 or p[0] == p[1] == boardSize - 1 or \
           (p[0] == 0 and p[1] == boardSize - 1) or (p[0] == boardSize - 1 and p[1] == 0):
            return moves[pos].pop(i)
 
    # Dirty scan for best moves
    for i in range(1, len(moves[pos])): # Start at pos 1 to avoid evaluating the key location
        p = moves[pos][i]
        if p[0] == 0 or p[0] == boardSize - 1 or p[1] == 0 or p[1] == boardSize - 1:
            return moves[pos].pop(i)
 
    # Dirty scan for second best moves
    for i in range(1, len(moves[pos])): # Start at pos 1 to avoid evaluating the key location
        p = moves[pos][i]
        if p[0] == 1 or p[0] == boardSize - 2 or p[1] == 1 or p[1] == boardSize - 2:
            return moves[pos].pop(i)
 
    # Dirty scan for third best moves - 9x9 board improves from 1.11 seconds to 0.79 seconds 
    # with this in place. 10x10 improves from 4 minutes to 6.3 seconds!  Even 11x11 completes 
    # in 2 minutes 4 seconds... this is certain proof that doing the outside first works
    # - which is not to say there aren't other winning methods...
    for i in range(1, len(moves[pos])): # Start at pos 1 to avoid evaluating the key location
        p = moves[pos][i]
        if p[0] == 2 or p[0] == boardSize - 3 or p[1] == 2 or p[1] == boardSize - 3:
            return moves[pos].pop(i)
 
    # Last test - improves 11x11 solve time down to 1.69 seconds!
    if boardSize > 6:
        for i in range(1, len(moves[pos])): # Start at pos 1 to avoid evaluating the key location
            p = moves[pos][i]
            if p[0] == 3 or p[0] == boardSize - 4 or p[1] == 3 or p[1] == boardSize - 4:
                return moves[pos].pop(i)
 
    # No valid best moves, just pop the last one.
    return moves[pos].pop()
 
 
 
def moveKnight((y, x)):
    global board, visited, moves # Global declarations - or Python chokes
    visited += 1                 # One more place visited
    board[y][x] = str(visited)   # Put the current move number in that position
    moves.append([knight])       # Add this location to the stack for later tries
    return                       # Note: only location added, not the moves from here
 
 
 
def backtrack((y, x)):
    global board, visited, moves
    moves.pop()          # Remove last (current) location from the stack
    visited -= 1         # Decrease the count of visited locations
    board[y][x] = ''
    if len(moves) > 0:   # Check we haven't backtracked right off the board
        knight = (moves[-1][-1])
        board[knight[0]][knight[1]] = ''   # Clear the board position
        #printBoard()
        return
    else:
        exitString = 'Found ' + str(len(tours)) + ' solutions, ' + str(tours.count('Closed')) \
                   + ' of which are closed'
        sys.exit(exitString) # We've backtracked off the board
 
 
 
def getMoves((y, x)):
    # Return a list of all possible moves on to the current board position.
    theList = [] # Store all the moves locally, add them after the return
 
    if y + 2 < boardSize:
        if x - 1 >= 0 and board[y+2][x-1] == "":
            theList.append((y+2, x-1))
        if x + 1 < boardSize and board[y+2][x+1] == "":
            theList.append((y+2, x+1))
 
    if x - 2 >= 0:
        if y - 1 >= 0 and board[y-1][x-2] == "":
            theList.append((y-1, x-2))
        if y + 1 < boardSize and board[y+1][x-2] == "":
            theList.append((y+1, x-2))
 
    if x + 2 < boardSize:
        if y - 1 >= 0 and board[y-1][x+2] == "":
            theList.append((y-1, x+2))
        if y + 1 < boardSize and board[y+1][x+2] == "":
            theList.append((y+1, x+2))
 
    if y - 2 >= 0:
        if x - 1 >= 0 and board[y-2][x-1] == "":
            theList.append((y-2, x-1))
        if x + 1 < boardSize and board[y-2][x+1] == "":
            theList.append((y-2, x+1))
 
    return theList
 
 
 
def printBoard():
    print boardSize*'+---' + '+'
    for i in range (boardSize):
        for p in range (boardSize):
            print '|%2s' %(board[i][p],),
        print '|\n' + boardSize*'+---' + '+'
    print
    #print '\nMoves =',len(moves)
    #x = raw_input() # This allows you to press enter between each move
    #sleep(sleepTime) # This allows you to slow the process down
    if len(moves) < boardSize**2: cls() # This clears the screen between each move
    return
 
 
 
def cls():
    os.system(['clear','cls'][os.name == 'nt'])
 
 
 
if __name__ == '__main__':
    startTime = time()              # Start the stopwatch
    main()                          # Run the solver to completion
    endTime = time()                # Stop the stopwatch
    totalTime = endTime - startTime # Calculate the time taken
    print 'This tour took',
    if totalTime >= 60:             # If it takes more than a minute
        print int(totalTime/60), 'minutes and', # Show how many minutes
    print '%.2f seconds' %(totalTime%60,)       # and/or the seconds