ruby - 使用 Warnsdorff 规则解决 Knights Tour

Question

我目前正在尝试使用 Warnsdorff 规则改进 Knight's Tour 的暴力执行，但是我觉得我好像不理解算法，因为脚本的执行需要很长时间。我主要是在寻找提示以指明正确的方向，以便我可以自己尽可能多地解决这个问题。谢谢!

这是我的代码:

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)
        current_move +=1
        board[x][y] = current_move

        puts board if current_move == 64
        exit if current_move == 64

        ordered_neighbors = 
            neighbors(x,y,board).sort_by { |m| m[:weight] }

        ordered_neighbors.each do |move|
            tour(move[:x], move[:y], Marshal.load(Marshal.dump board), current_move)
        end
        false
    end

    def weight(x,y,board)
        possible = 0
        moves(x,y).each do |move|
            next unless valid_move?(move, board)
            possible +=1
        end
        possible
    end

    def neighbors(x,y,board)
        neighbors = []
        moves(x,y).each do |move|
            next unless valid_move?(move, board)
            neighbors << { weight: weight(move[:x], move[:y], board), 
                                x: move[:x], y: move[:y] }
        end
        neighbors
    end

    def valid_move?(move,board)
        x = move[:x]
        y = move[:y]
        !(board[x] == nil || board[x][y] == nil || 
          board[x][y] != 0 || x < 0 || y < 0)
    end

    def moves(x,y)
        [{x: x+2, y: y-1}, 
         {x: x+1, y: y-2}, 
         {x: x-1, y: y-2}, 
         {x: x-1, y: y+2}, 
         {x: x+1, y: y+2}, 
         {x: x-2, y: y+1}, 
         {x: x-2, y: y-1}]
    end
end

KnightsTour.new

Answer 1

优化

我会怀疑在以下方面花费的时间:

Marshal.load(Marshal.dump board)

另一种方法是使用董事会的单一副本。

在游览开始时您设置:

board[x][y] = current_move

因此，如果在游览结束时您使用以下方式清除它:

board[x][y] = 0

那么你应该不需要制作电路板的副本。

错误

请注意，骑士有 8 步合法移动!

尝试添加:

{x: x+2, y: y+1}