Algorithm for knight's tour on a 6x6 array only works on index [0, 0]

Question

I must mention that this is my first time posting on this site, forgive me if I don't follow this site's guidelines to the tee.

My problem is probably simple but I can't understand it. My knight's tour algorithm recursively finds a path for a knight. It works on index [0,0], it iterates through the spaces of the array perfectly... however, on anything but index [0,0], the program hangs for what seems like an eternity. Here is my code:

# knightstour.py
#
# created by: M. Peele
# section: 01
# 
# This program implements a brute-force solution for the Knight's tour problem 
# using a recursive backtracking algorithm. The Knight's tour is a chessboard 
# puzzle in which the objective is to find a sequence of moves by the knight in 
# which it visits every square on the board exactly one. It uses a 6x6 array for 
# the chessboard where each square is identified by a row and column index, the 
# range of which both start at 0. Let the upper-left square of the board be the 
# row 0 and column 0 square.
#
# Imports the necessary modules.
from arrays import *

# Initializes the chessboard as a 6x6 array. 
chessBoard = Array2D(6, 6)

# Gets the input start position for the knight from the user.
row = int(input("Enter the row: "))
col = int(input("Enter the column: "))

# Main driver function which starts the recursion.
def main():
    knightsTour(row, col, 1)

# Recursive function that solves the Knight's Tour problem.    
def knightsTour(row, col, move):
    # Checks if the given index is in range of the array and is legal.
    if _inRange(row, col) and _isLegal(row, col): 
        chessBoard[row, col] = move # Sets a knight-marker at the given index.
        # If the chessBoard is full, returns True and the solved board.
        if _isFull(chessBoard):
            return True, _draw(chessBoard)    

        # Checks to see if the knight can make another move. If so, makes that 
        # move by calling the function again. 
        possibleOffsets = ((-2, -1), (-2, 1), (-1, 2), (1, 2), \
                           (2, 1), (2, -1), (1, -2), (-1, -2))
        for offset in possibleOffsets:
            if knightsTour(row + offset[0], col + offset[1], move + 1):
                return True 
        # If the loop terminates, no possible move can be made. Removes the 
        # knight-marker at the given index. 
        chessBoard[row, col] = None
        return False 
    else:
        return False

# Determines if the given row, col index is a legal move.
def _isLegal(row, col):
    if _inRange(row, col) and chessBoard[row, col] == None:
        return True
    else:
        return False

# Determines if the given row, col index is in range.
def _inRange(row, col):
    try:
        chessBoard[row, col]
        return True
    except AssertionError:
        return False

# A solution was found if the array is full, meaning that every element in the 
# array is filled with a number saying the knight has visited there.
def _isFull(chessBoard):
    for row in range(chessBoard.numRows()):
        for col in range(chessBoard.numCols()):
            if chessBoard[row, col] == None:
                return False
    return True

# Draws a pictoral representation of the array.
def _draw(chessBoard):
    for row in range(chessBoard.numRows()):
        for col in range(chessBoard.numCols()):
            print("%4s" % chessBoard[row, col], end = " ")
        print()

# Calls the main function.
main()

Please give us an SSCCE. We can't run this without your arrays module, and there's a whole lot of code that's probably irrelevant to the problem. — abarnert
Meanwhile, replacing your Array2D with just a list of lists, your code works for me on every input I throw at it, including (0,1), (0,3), (1,3), (2,5), and (5,2). So, it seems like whatever the problem is, it may be somewhere in your Array2D implementation, not this code. — abarnert
My Array2D module is essentially a list of lists as far as my instructor has said, so if the problem lies with that module, am I just stuck? — Miles Peele
Can you post the Array2D implementation here, or on pastebin or something? If nobody can run your code, nobody can debug it. — abarnert
I would if I could, the .pyc module that the Array2D implementation is in is a bunch of dark letters. There's no discernible code — Miles Peele

abarnert abarnert · Accepted Answer · 2013-04-08T22:54:30

There is nothing obviously wrong with your code. And, in fact, replacing chessBoard with a list of lists and changing the rest of the code appropriately, it works for all legal inputs.

See this pastebin for the adapted code. See this one for a modified version that just loops over all valid inputs. If you run it, it prints out exactly 36 completed boards.

So, if there is a problem either you're not running the same code you posted here, or there's a bug in your Array2D implementation.

There are a few weird things about your code.

First, you almost never want to check == None. If you really need to check whether something is None, use the is operator, not ==. If all of your "real" values are truthy, just use the value itself as a boolean (because None is falsey). See Programming Recommendations in PEP 8 for details.

Next, you have your global setup split between a main function, and global module scope. Usually you want to do it all in the same place.

Finally, having a recursive function that mutates a global variable is an odd thing to do. Not that it doesn't work in your case (but only because you can only ever run one test before exiting), but usually in a recursive function you want to either pass the value down as an "accumulator" argument, or do everything immutably (by passing copies down and back up).

Algorithm for knight's tour on a 6x6 array only works on index [0, 0]

2 Answers