Knight's Tour

My son, currently in 9th grade, has been pestering me to learn Python or Java or something else instead of reading Facebook all the time. So finally I gave in and told him to setup Python on one of the old unused desktop. He installed Ubuntu, Python, some editor called "ATOM" and some linter for Python program. Python seems to be very easy. There are lots of good material available. Whatever question I had, I got answer from stack overflow. As first program in Python I wanted to try Knight's tour. It took some time but I could complete it. Here is the code for Knight's tour.

# import copy boardPostions = [] solutionNumber = 0 def getEmptyBoard(): """Get empty board.""" emptyBoard = [[0, 0, 0, 0, 0, 0, 0, 0], # Row number 1 [0, 0, 0, 0, 0, 0, 0, 0], # Row Number 2 [0, 0, 0, 0, 0, 0, 0, 0], # Row Number 3 [0, 0, 0, 0, 0, 0, 0, 0], # Row Number 4 [0, 0, 0, 0, 0, 0, 0, 0], # Row Number 5 [0, 0, 0, 0, 0, 0, 0, 0], # Row Number 6 [0, 0, 0, 0, 0, 0, 0, 0], # Row Number 7 [0, 0, 0, 0, 0, 0, 0, 0], # Row Number 8 [0, 0, 0]] # row and column position of knight and current move number return emptyBoard def printBoard(singleBoardPosition): """Print board postions.""" global solutionNumber print("===", solutionNumber, singleBoardPosition[8][0], singleBoardPosition[8][1], singleBoardPosition[8][2], ":") if singleBoardPosition[8][2] > 63: solutionNumber = solutionNumber + 1 for i in range(8): for j in range(8): print("%3d" % (singleBoardPosition[i][j]), end="") print() def copyBoardElements(b1, b2): """Copy board elements.""" if b1 is None: print("copyBoardElements, b1 is None") if b2 is None: print("copyBoardElements, b2 is None") for cp1 in range(8): for cp2 in range(8): b1[cp1][cp2] = b2[cp1][cp2] b1[8][0] = b2[8][0] b1[8][1] = b2[8][1] b1[8][2] = b2[8][2] def canReachFrom2Squares(board): """Check if all empty postions can be reached from two other positions.""" # # Function to check if board has an empty square that can not be reached from 2 or more squares # i = 0 j = 0 totalCannotReach = 0 if board[8][2] >= 58: # print("Return from top line") return True # else: # print('Current postion on the board is ', board[8][2]) # print("checking unreacheable squares", i, j) for i in range(8): for j in range(8): canReach = 0 if board[i][j] == 0: newRow = i+2 newCol = j+1 # print ("checking 1", newRow, newCol) if canReach < 2 and newRow in range(0, 8) and newCol in range(0, 8) and board[newRow][newCol] == 0: canReach = canReach+1 # print("Can reach Number-1") # newRow = i+2 newCol = j-1 # print ("checking 2", newRow, newCol) if canReach < 2 and newRow in range(0, 8) and newCol in range(0, 8) and board[newRow][newCol] == 0: canReach = canReach+1 # print("Can reach Number-2") # newRow = i-2 newCol = j+1 # print ("checking 3", newRow, newCol) if canReach < 2 and newRow in range(0, 8) and newCol in range(0, 8) and board[newRow][newCol] == 0: canReach = canReach+1 # print("Can reach Number-3") # newRow = i-2 newCol = j-1 # print("checking 4", newRow, newCol) if canReach < 2 and newRow in range(0, 8) and newCol in range(0, 8) and board[newRow][newCol] == 0: canReach = canReach+1 # print("Can reach Number-4") # newRow = i+1 newCol = j+2 # print("checking 5", newRow, newCol) if canReach < 2 and newRow in range(0, 8) and newCol in range(0, 8) and board[newRow][newCol] == 0: canReach = canReach+1 # print("Can reach Number-5") # newRow = i+1 newCol = j-2 # print("checking 6", newRow, newCol) if canReach < 2 and newRow in range(0, 8) and newCol in range(0, 8) and board[newRow][newCol] == 0: canReach = canReach+1 # print("Can reach Number-6") # newRow = i-1 newCol = j+2 # print("checking 7", newRow, newCol) if canReach < 2 and newRow in range(0, 8) and newCol in range(0, 8) and board[newRow][newCol] == 0: canReach = canReach+1 # print("Can reach Number-7") # newRow = i-1 newCol = j-2 # print("checking 8", newRow, newCol) if canReach < 2 and newRow in range(0, 8) and newCol in range(0, 8) and board[newRow][newCol] == 0: canReach = canReach+1 # print("Can reach Number-8") # # print("canReach value = ", canReach) if canReach < 2: totalCannotReach = totalCannotReach+1 if totalCannotReach > 1: # print("all not reachable from two positions", i, j) # printBoard(board) return False return True def makeInitialMove(): """Make initial move on the board.""" for i in range(0, 8): for j in range(0, 8): initBoard = getEmptyBoard() initBoard[i][j] = 1 initBoard[8][0] = i initBoard[8][1] = j initBoard[8][2] = 1 boardPostions.append(initBoard) def makeSingleMove(i, j, k, board): """Make knight move onthe board.""" # check if new position is in the board or out of board and postion should be empty if i in range(0, 8) and j in range(0, 8) and board[i][j] == 0: newBoard = getEmptyBoard() copyBoardElements(newBoard, board) # newBoard[8][2] = k # before making a move, check if every position can be reached from two other postions # no need to perform that check if knight is moving for the first time # no need to check if knight has already traversed all blocks, goal achieved. if k == 64 or canReachFrom2Squares(newBoard): newBoard[i][j] = k newBoard[8][0] = i newBoard[8][1] = j newBoard[8][2] = k if k == 64: print("Knight traversed whole board without repeating any block", end="") printBoard(newBoard) else: # if knight traversed all block then why put board back on the stack? boardPostions.append(newBoard) # else: # printBoard(newBoard) # print("it will make board unreachable if knight move to ", i, j, "for move number=", k) def makeKnightmove(): """Make knight move.""" if boardPostions[len(boardPostions)-1] is None: return 1 currentBoardPostion = getEmptyBoard() # copyBoardElements(currentBoardPostion, boardPostions[len(boardPostions)-1]) # # print("Removing last board") # boardPostions.pop() currentBoardPostion = boardPostions.pop() row = currentBoardPostion[8][0] col = currentBoardPostion[8][1] moveNumber = currentBoardPostion[8][2] makeSingleMove(row+2, col+1, moveNumber+1, currentBoardPostion) makeSingleMove(row+2, col-1, moveNumber+1, currentBoardPostion) makeSingleMove(row-2, col+1, moveNumber+1, currentBoardPostion) makeSingleMove(row-2, col-1, moveNumber+1, currentBoardPostion) makeSingleMove(row-1, col+2, moveNumber+1, currentBoardPostion) makeSingleMove(row-1, col-2, moveNumber+1, currentBoardPostion) makeSingleMove(row+1, col+2, moveNumber+1, currentBoardPostion) makeSingleMove(row+1, col-2, moveNumber+1, currentBoardPostion) # return moveNumber+1 # solutionNumber = 0 # for i in range(8): # for j in range(8): # # boardPostions.append(makeMove(i, j, 1, None)) # intialBoard = getEmptyBoard() # makeSingleMove(i, j, 1, None) print("Make initial moves. it will put 64 boards each board representing initial position of knight.") makeInitialMove() print("Now start making moves after initial moves.") loop_count = 0 current_move = 1 while True: # print("") # print("loop number", loop_count, "Number of boards", len(boardPostions)) makeKnightmove() loop_count = loop_count+1 if len(boardPostions) == 0: break