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

i must mention first time posting on site, forgive me if don't follow site's guidelines tee.

my problem simple can't understand it. knight's tour algorithm recursively finds path knight. works on index [0,0], iterates through spaces of array perfectly... however, on index [0,0], program hangs seems eternity. here code:

# knightstour.py # # created by: m. peele # section: 01 #  # program implements brute-force solution knight's tour problem  # using recursive backtracking algorithm. knight's tour chessboard  # puzzle in objective find sequence of moves knight in  # visits every square on board one. uses 6x6 array  # chessboard each square identified row , column index,  # range of both start @ 0. let upper-left square of board  # row 0 , column 0 square. # # imports necessary modules. arrays import *  # initializes chessboard 6x6 array.  chessboard = array2d(6, 6)  # gets input start position knight user. row = int(input("enter row: ")) col = int(input("enter column: "))  # main driver function starts recursion. def main():     knightstour(row, col, 1)  # recursive function solves knight's tour problem.     def knightstour(row, col, move):     # checks if given index in range of array , legal.     if _inrange(row, col) , _islegal(row, col):          chessboard[row, col] = move # sets knight-marker @ given index.         # if chessboard full, returns true , solved board.         if _isfull(chessboard):             return true, _draw(chessboard)              # checks see if knight can make move. if so, makes          # move calling function again.          possibleoffsets = ((-2, -1), (-2, 1), (-1, 2), (1, 2), \                            (2, 1), (2, -1), (1, -2), (-1, -2))         offset in possibleoffsets:             if knightstour(row + offset[0], col + offset[1], move + 1):                 return true          # if loop terminates, no possible move can made. removes          # knight-marker @ given index.          chessboard[row, col] = none         return false      else:         return false  # determines if given row, col index legal move. def _islegal(row, col):     if _inrange(row, col) , chessboard[row, col] == none:         return true     else:         return false  # determines if given row, col index in range. def _inrange(row, col):     try:         chessboard[row, col]         return true     except assertionerror:         return false  # solution found if array full, meaning every element in  # array filled number saying knight has visited there. def _isfull(chessboard):     row in range(chessboard.numrows()):         col in range(chessboard.numcols()):             if chessboard[row, col] == none:                 return false     return true  # draws pictoral representation of array. def _draw(chessboard):     row in range(chessboard.numrows()):         col in range(chessboard.numcols()):             print("%4s" % chessboard[row, col], end = " ")         print()  # calls main function. main() 

there nothing wrong code. and, in fact, replacing chessboard list of lists , changing rest of code appropriately, works legal inputs.

see this pastebin adapted code. see this one modified version loops on valid inputs. if run it, prints out 36 completed boards.

so, if there problem either you're not running same code posted here, or there's bug in array2d implementation.

---

there few weird things code.

first, never want check == none. if need check whether none, use is operator, not ==. if of "real" values truthy, use value boolean (because none falsey). see programming recommendations in pep 8 details.

next, have global setup split between main function, , global module scope. want in same place.

finally, having recursive function mutates global variable odd thing do. not doesn't work in case (but because can ever run 1 test before exiting), in recursive function want either pass value down "accumulator" argument, or immutably (by passing copies down , up).