Возникли проблемы с Knights Tour в Ruby

Я пытаюсь решить проблему рыцарского тура как упражнение в рекурсии, так как я не использовал его некоторое время, но мой сценарий, похоже, не находит решения и достигает только 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

ruby algorithm knights-tour
person xxyyxx    schedule 18.07.2017    source источник
comment
tour(x+2, y-1, board, current_move) попробует ячейку 2, 6 присвоить [x,y] == [0,0], поскольку ruby ​​позволяет обращаться ко «второму с конца» элементу как array[-2].   -  person Aleksei Matiushkin    schedule 18.07.2017
comment
Хороший улов, спасибо! Обновление оператора return для учета этого, похоже, даст мне еще 1 ход до 57.   -  person xxyyxx    schedule 18.07.2017

Ответы (2)


arrow_upward
1
arrow_downward

Основная проблема заключается в том, что вы используете только один объект board для всех рекурсий. Вы должны использовать копию board каждый раз, когда пытаетесь сделать ход. dup создает поверхностную копию, и этого недостаточно для дублирования доски.

Другая проблема может заключаться в том, что подход грубой силы слишком медленный из-за экспоненциального роста (8 ходов на каждой итерации, даже если вы останавливаетесь раньше для некоторых).

Обычный подход состоит в том, чтобы выбрать ячейку с наименьшими возможностями в качестве следующего хода.

person Eric Duminil    schedule 18.07.2017
comment
Еще один хороший совет — начать с доски 3×3 и отслеживать, что происходит. - person Aleksei Matiushkin; 18.07.2017
comment
@mudasobwa: Невозможно решить доску 3x3: как бы вы приземлились на среднюю клетку? - person Eric Duminil; 18.07.2017
comment
Не беда, первые 10 проблем при таком подходе возникнут уже на 3х3 :) - person Aleksei Matiushkin; 18.07.2017
comment
Спасибо! Я неправильно понял, как параметр Ruby передает слова, теперь я обманываю доску, когда передаю ее. Я надеюсь получить решение грубой силы, а затем работать над повышением его эффективности. - person xxyyxx; 18.07.2017
comment
@xxyyxx: dup недостаточно: a = [[0,0],[0,0]]; b=a.dup; b[0][0]=1; a - person Eric Duminil; 18.07.2017
comment
Спасибо, Эрик, я ценю, что вы указали мне правильное направление, а не просто предложили решение. Сейчас я использую Marshal.load (плата Marshal.dump), и это, похоже, работает, учитывая, как долго выполняется скрипт. Теперь я буду работать над тем, чтобы превратить метод грубой силы во что-то более эффективное. - person xxyyxx; 18.07.2017

arrow_upward
0
arrow_downward 

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

вот рубиновая версия, которая работает. Хитрость этого решения заключается в том,

  1. не помещайте никаких отладочных сообщений в рекурсивный метод.
  2. передать xmoves и ymoves как переменную рекурсивному методу. не определяйте константу KNIGHTS_MOVES = [[2, 1],[2, -1], [-2, 1],[-2, -1],[ 1, 2], [1, -2], [-1, 2], [-1, -2]] и перебрать его вsolve_nt_helper. size.each будет генерировать много объектов Enumerator, но итератор над константой, похоже, замедляет весь процесс.

трюк 1 также кажется применимым к java и python. не пробовал item2 для java и python. Алгоритм позаимствован у geekstogeeks

person caiyun liu    schedule 12.09.2020