I try to solve Knight tour problem with python and backtracking, but the code doesn't respond likely I want... This is my code in python:
import random
board = [
[0,0,0,0,0,0],
[0,0,0,0,0,0],
[0,0,0,0,0,0],
[0,0,0,0,0,0],
[0,0,0,0,0,0],
[0,0,0,0,0,0]
]
intialCell = [random.randint(0,5),random.randint(0,5)]
path = []
def besideCells(s):
moves = [
(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)
]
return [[s[0] + dx, s[1] +dy] for dx,dy in moves
if 0 <= s[0] +dx < 6 and 0 <= s[1] +dy < 6 and board[s[0] +dx][s[1] +dy] == 0]
def choose(board,s,path):
for l in board:
print(l)
print(path)
print('---###---')
varbesideCells = besideCells(s)
path.append(s)
board[s[0]][s[1]] = len(path)
if len(path) == 36:
return True #str(path)
if not varbesideCells:
return False
found = False
for cells in varbesideCells:
if choose(board,cells,path):
return True
path.pop()
board[s[0]][s[1]] = 0
return found
print(intialCell)
print(besideCells(intialCell))
print(choose(board,intialCell,path))
The besideCells function return a list that have the allowed cells in the board can be chosen The choose function try to add a cell to the path and continue until don't exist a valid cell for a tour, with recursive and backtracking algorithm...
The algorithm does not always produce a valid tour, leading to duplicate numbers or incomplete paths.
I tried rearranging function calls, but this did not solve the issue.
The problem is that your code can return False without undoing the latest update you made to path and board.
To solve this, just remove the following lines:
if not varbesideCells:
return False
If now that condition is true (i.e. varbesideCells is an empty list), then execution will continue as follows: it will not make any iteration of the loop, and so the boolean found will be False. But now the two updates to path and board are properly reverted before that False is returned.
Your functions have some dependencies on global variables (e.g. board in besideCells) and hardcoded constants (like 5, 6 and 36). It would be better to avoid havinng board and path as global variables. Instead, pass all needed variables as arguments and support different board sizes.
For debugging purposes it would seem more useful to print the board and path after they have been updated.
Some names are misleading or strange:
varbesideCells is an odd name (starting with var). You could call this neighbors, and the function that retrieves them get_neighbors.cells is not a collection of multiple cells; it is one cell. In the context where you use it, it could be named neighbors doesn't really give much information what it is about. This could be named cell.If you use randrange instead of randint, you can use the size of the board as argument.
There is much more that could be improved, but with the above remarks, it could already look like this:
from random import randrange
def get_neighbors(board, cell):
n = len(board)
moves = [
(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)
]
return [[cell[0] + dx, cell[1] + dy]
for dx, dy in moves
if 0 <= cell[0] + dx < n and 0 <= cell[1] + dy < n
and board[cell[0] + dx][cell[1] + dy] == 0]
def choose(board, cell, path):
path.append(cell)
board[cell[0]][cell[1]] = len(path)
# If you want to print the board for debugging, do it here. But
# the size of the output will grow exponentially.
if len(path) == len(board) ** 2:
return True #str(path)
neighbors = get_neighbors(board, cell)
found = False
for neighbor in neighbors:
if choose(board, neighbor, path):
return True
path.pop()
board[cell[0]][cell[1]] = 0
return found
def find_knight_path(n):
board = [[0] * n for _ in range(n)]
intialCell = [randrange(n), randrange(n)]
found = choose(board, intialCell, [])
return board if found else None
solution = find_knight_path(5)
if solution:
for row in solution:
print(row)
else:
print("No solution found. Maybe try again from a different starting point.")
Finally, this algorithm will not be suitable for much larger boards, as it will need to backtrack a lot. You could have a look at Warnsdorff's rule.