Problem Statement: Given a N*N board with the Knight placed on the first block of an empty board. Moving according to the rules of chess knight must visit each square exactly once. Print the order of each cell in which they are visited on the chess board. If there are more than one solutions possible, print all of them.
Input :
N = 8
Output:
0 59 38 33 30 17 8 63
37 34 31 60 9 62 29 16
58 1 36 39 32 27 18 7
35 48 41 26 61 10 15 28
42 57 2 49 40 23 6 19
47 50 45 54 25 20 11 14
56 43 52 3 22 13 24 5
51 46 55 44 53 4 21 12
I tried a recursive solution using backtracking but do not quite understand what could be the problem with this piece of code. Could someone please help. Thanks a lot!
for n=2,3,4 it produces an empty list which is expected.
and for n=5, it produces the following unexpected output:
[[[0, '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.']], [[0, '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.']]] ..continues
for n=8, the program keeps running and does not seem to produce an output for a long time
def knight(n):
xy_movements = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(-1,2),(1,-2),(-1,-2)]
board = [["."]*n for _ in range(n)]
board[0][0]=0
current_x=0
current_y=0
result=[]
def backtrack(num):
nonlocal n,current_x,current_y
if num==(n*n)-1:
result.append(board)
return
else:
for move in xy_movements:
if current_x+move[0]<0 or current_x+move[0]>=n or\
current_y+move[1]<0 or current_y+move[1]>=n or\
board[current_x+move[0]][current_y+move[1]] !=".":
continue
else:
current_x+=move[0]
current_y+=move[1]
board[current_x][current_y] = num+1
backtrack(num+1)
board[current_x][current_y] = "."
current_x -= move[0]
current_y -= move[1]
backtrack(0)
return result
The problem is that result.append(board) will append the only board you have, while your backtracking algorithm will continue to update that board, and at the very end of the algorithm will have taken back all moves it did. So then board is empty, except for the first 0 that was placed and never removed. This means that in result you now reference an almost empty board, even though solutions were found.
The solution is simple: take a copy of the board, and append that board to the result list:
result.append([row[:] for row in board])
This will solve the issue you mention when calling knight(5). For boards larger than 6, you will just have a problem that is too great: there are 19,591,828,170,979,904 solutions for an 8x8 board, so don't hope to get that in a few seconds. Your PC will probably not have enough memory to collect that many boards, let be you can wait for it.