I'm trying to the knights tour problem as an exercise in recursion since I have not used it in awhile, but my script does not seem to find a solution and only goes as high as 56 moves. Any tips to point me in the right direction would be appreciated.
class KnightsTour
def initialize
board = [nil, nil, nil, nil, nil, nil, nil, nil]
8.times do |i|
board[i] = [0, 0, 0, 0, 0, 0, 0, 0]
end
tour(0,0,board)
end
def tour(x,y,board,current_move=0)
puts board if current_move == 64
return if board[x] == nil ||
board[x][y] == nil ||
board[x][y] != 0 ||
x < 0 ||
y < 0 ||
current_move == 64
current_move +=1
board[x][y] = current_move
tour(x+2, y+1, board.dup, current_move)
tour(x+2, y-1, board.dup, current_move)
tour(x+1, y-2, board.dup, current_move)
tour(x-1, y-2, board.dup, current_move)
tour(x-1, y+2, board.dup, current_move)
tour(x+1, y+2, board.dup, current_move)
tour(x-2, y+1, board.dup, current_move)
tour(x-2, y-1, board.dup, current_move)
end
end
KnightsTour.new
The main problem is that you only use one board object for all the recursions. You should use a copy of board anytime you try a move. dup produces a shallow copy, and isn't enough to duplicate the board.
Another problem might be that the bruteforce approach is too slow because of exponential growth (8 moves at every iteration, even if you stop early for some).
The usual approach is to pick the cell having the fewest possibilities as the next move.