Knight's Tour

gistfile1.txt

board = []
board_size = -1

def initiateBoard (board_dimensions):
    global board
    global board_size
    global knights_moves
    board_size = board_dimensions
    for i in range(0, board_size):
        board.append(board_size*[0])
knights_moves = ((-2,-1),(1,2),(2,-1),(-2,1),(2,1),(-1,2),(1,-2),(-1,-2))
def isAvailable(x, y):
    if x < len(board) and y < len(board[0]) and \
       x >= 0 and y >= 0 and board[x][y]==0:
        return True
    else:
        return False
def getPossibleMoves(x, y):
     possible_moves = []
     for move in knights_moves: 
        cx,cy = x+move[0], y+move[1]
        if isAvailable(cx,cy):
            possible_moves.append((move[0],move[1]))
     return possible_moves  

def getNumMoves(x, y):
     return len(getPossibleMoves(x, y)) 
 
def getNextMove (numMoves):
    smallestIndex = 0
    if not numMoves:    #Nowhere to go
        drawBoard()    #Show the results                      
        sys.exit(1) 
    smallest = numMoves[0]
    for i in range(len(numMoves)):
        if numMoves[i] < smallest:
            smallest = numMoves[i]
            smallestIndex = i

    return smallestIndex

def solve (x,y,num_move):
    assert board[x][y] == 0
    board[x][y] = num_move                                  
    possible_moves = getPossibleMoves(x,y)
    numOfMoves = []      
    for move in possible_moves:
        numOfMoves.append(getNumMoves(x+move[0],y+move[1]))
    nextMove = possible_moves[getNextMove(numOfMoves)]
    solve(x+nextMove[0],y+nextMove[1],num_move+1)   

def getKnightsPath (board_dimensions):
    initiateBoard (board_dimensions)
    solve(0,0,1)