Skip to content

Instantly share code, notes, and snippets.

@sanchojaf
Last active July 30, 2017 11:30
Show Gist options
  • Save sanchojaf/19e33bafc0a0085f09f82cd2141106b4 to your computer and use it in GitHub Desktop.
Save sanchojaf/19e33bafc0a0085f09f82cd2141106b4 to your computer and use it in GitHub Desktop.
Knight’s Tour Problem [backtracking, ruby]
# A knight’s tour is a sequence of moves of a knight on a chessboard such that
# the knight visits every square only once. If the knight ends on a square that
# is one knight’s move from the beginning square (so that it could tour the board
# again immediately, following the same path), the tour is closed, otherwise it is open.
class KnightTour
def initialize(n)
@n = n
@path = 0
@board = Array.new(n) { Array.new(n, 0) }
end
def solve
if find_path(0, 0, 0) then print_board else puts "NO PATH FOUND" end
end
def find_path(row, col, index)
return false if @board[row][col] != 0
@path += 1
@board[row][col] = @path
return true if index == @n*@n-1
variations = [[2,1],[2,-1],[1,2],[1,-2],[-1,2],[-1,-2],[-2,1],[-2,-1]]
variations.each do |var_row, var_col|
if can_move?(row+var_row, col+var_col)
return true if find_path(row+var_row, col+var_col, index+1)
end
end
@board[row][col] = 0
@path -= 1
false
end
def can_move?(row, col)
row.between?(0,@n-1) and col.between?(0,@n-1)
end
def print_board
puts "Board:"
@board.each do |row|
row.each do |value|
print value < 10 ? " #{value} " : "#{value} "
end
puts
end
end
end
n = 6
i = KnightTour.new(n)
i.solve
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment