Ruby 中的 Knights Tour 遇到问题

Question

我正在尝试将骑士巡回赛问题作为递归练习，因为我已经有一段时间没有使用它了，但我的脚本似乎没有找到解决方案，而且最多只有 56 步。任何能为我指明正确方向的提示都将不胜感激。

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

Answer 1

主要问题是您只对所有递归使用一个 board 对象。任何时候尝试移动都应该使用 board 的副本。 dup 生成浅拷贝，不足以复制电路板。

另一个问题可能是由于指数增长，蛮力方法太慢了（每次迭代 8 次移动，即使你提前停止了一些）。

通常的做法是选择可能性最小的单元格作为下一步。

Answer 2

def is_safe?(solution, x, y)
   x >= 0 && x < solution.length && y>= 0 && y < solution.length && solution[x][y] == -1
end

def solve_nt_helper(size, solution, curr_x, curr_y, num, xmoves, ymoves)
    return true if num == size * size
    size.times.each do |i|
        # p "i:#{i}"
        next_x = curr_x + xmoves[i]
        next_y = curr_y + ymoves[i]
        if is_safe?(solution, next_x, next_y)
            solution[next_x][next_y] = num
            return true if solve_nt_helper(size, solution, next_x, next_y, num + 1, xmoves, ymoves)
  
            solution[next_x][next_y] = -1
        end
    end
    # p "failed at num #{num}"
    false
end

def solve_nt(n)
    xmoves = [2, 1, -1, -2, -2, -1, 1, 2]
    ymoves = [1, 2, 2, 1, -1, -2, -2, -1]
    solution = Array.new(n) { Array.new(n) { -1 } }
    solution[0][0] = 0
    solution.each do |row|
      p row
    end
    return 'invalid' unless solve_nt_helper(n, solution, 0, 0, 1, xmoves, ymoves)
    solution.each do |row|
      p row
    end
    solution
end

n = 8
require 'memory_profiler'
report = MemoryProfiler.report do
solve_nt(n)
end
report.pretty_print

这是一个可用的 ruby 版本。这个解决方案的技巧是

不要在递归方法中放置任何调试信息。
将 xmoves 和 ymoves 作为变量传递给递归 method.don不定义常量 KNIGHTS_MOVES = [[2, 1],[2, -1], [-2, 1],[-2, -1],[1, 2],[1, -2], [- 1, 2], [-1, -2]] 并在 solve_nt_helper 中对其进行迭代。 sizes.each 会生成很多 Enumerator 对象，但是对常量的迭代器似乎会减慢整个过程。

技巧 1 似乎也适用于 java 和 python.did 不要尝试 java 和 python 的项目 2。算法借鉴自geekstogeeks

Ruby 中的 Knights Tour 遇到问题

Having trouble with Knights Tour in Ruby

ruby

algorithm

knights-tour