Solve knights tour both recursively and iteratevely

knights_tour.rb

# A knight is placed on a square of the board, moving according to the rules of the chess he must visit each square exactly once

N = 8

sol = Array.new(N) { Array.new(N) { :not_visited } }

def print_solution(sol)
  sol.each do |line|
    line.each { |char| print "#{char} " }
    puts
  end
end

def safe_to_move?(x, y, sol)
  x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == :not_visited
end

x_moves = [2, 1, -1, -2, -2, -1, 1, 2]
y_moves = [1, 2, 2, 1, -1, -2, -2, -1]

sol[0][0] = 0

def solve_recursive(x, y, move_index, sol, x_moves, y_moves)
  return true if move_index == N * N

  x_moves.zip(y_moves)
    .map { |x_move, y_move| [x + x_move, y + y_move] }
    .each do |next_x, next_y|
    if safe_to_move?(next_x, next_y, sol)
      sol[next_x][next_y] = move_index
      if solve_recursive(next_x, next_y, move_index + 1, sol, x_moves, y_moves)
        return true
      else
        sol[next_x][next_y] = :not_visited
      end
    end
  end
  false
end

# solve_recursive(0, 0, 1, sol, x_moves, y_moves) ? print_solution(sol) : p('No solution unfortunately')

# 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
#
# 0 5 14 9 20
# 13 8 19 4 15
# 18 1 6 21 10
# 7 12 23 16 3
# 24 17 2 11 22

Stack = Struct.new(:x, :y, :move_count, :move_index)

def solve_interative(x, y, move_count, sol, x_moves, y_moves)
  current_x, current_y, current_move_count, move_index = x, y, move_count, 0
  stack = [Stack.new(current_x, current_y, current_move_count, move_index)]
  sol[current_x][current_y] = 0

  until stack.empty?
    if current_move_count == N * N
      return true
    end

    pop = stack.pop
    current_x, current_y, current_move_count, move_index = pop.x, pop.y, pop.move_count, pop.move_index

    while move_index < x_moves.length
      next_x = current_x + x_moves[move_index]
      next_y = current_y + y_moves[move_index]

      if safe_to_move?(next_x, next_y, sol)
        sol[next_x][next_y] = current_move_count
        stack.push(Stack.new(current_x, current_y, current_move_count, move_index + 1))
        current_move_count += 1
        stack.push(Stack.new(next_x, next_y, current_move_count, 0))
        break
      else
        move_index += 1
      end
    end

    if move_index == x_moves.length
      sol[current_x][current_y] = :not_visited
    end
  end

  false
end

solve_interative(0, 0, 1, sol, x_moves, y_moves) ? print_solution(sol) : p('No solution unfortunately')