layton1.rb

def solve
  hs = [
    [5, 3, 1, 2, 4],
    [2, 5, 1, 4, 3],
    [0, 0, 0, 0, 0],
  ]

  queue = [[]]
  checks = {}
  checks[hs.map{|h| h.join(',')}.join('|')] = true
  ps_size = nil
  count = 0

  until queue.empty?
    ps = queue.shift
    hs1 = hs.map(&:dup)
    ps.each do |(a1, a2, b1, b2)|
      hs1[a1][a2], hs1[b1][b2] = hs1[b1][b2], hs1[a1][a2]
    end
    if hs1.select { |h| h == [5, 4, 3, 2, 1] }.size == 2
      p ps
      break
    end
    # 28手まで
    next if ps.size == 28
    if ps_size != ps.size
      p [ps.size, count]
      count = 0
    end
    ps_size = ps.size
    count += 1

    ns = hs1.map { |h| h.index(0) }
    hs1.each_with_index do |h, i|
      n = ns[i]
      next unless n
      a1, a2 = i, n
      [1, 2].each do |d|
        j = (i + d) % hs.size
        m = ns[j]&.pred || 4
        b1, b2 = j, m
        hs1[a1][a2], hs1[b1][b2] = hs1[b1][b2], hs1[a1][a2]
        error = hs1.each_with_index.map do |h, k|
          e = ns[k]&.pred || 4
          h.each_with_index.map { |x, f| f > e || (5 - f) == x ? 0 : e - f }.sum
        end.sum
        key = hs1.map{|h| h.join(',')}.join('|')
        unless checks[key] || ps.size + error > 28
          queue.push(ps + [[a1, a2, b1, b2]])
        end
        checks[key] = true
        hs1[a1][a2], hs1[b1][b2] = hs1[b1][b2], hs1[a1][a2]
      end
    end
  end
end

solve

layton2.rb

BOARD = []
6.times do |i|
  BOARD[i] = []
  6.times do |j|
    BOARD[i][j] = 0
  end
end
WANT = [[1, 1, 1, 3, 3, 3],
        [1, 0, 0, 0, 0, 3],
        [6, 6, 0, 0, 7, 7],
        [5, 6, 0, 0, 7, 2],
        [5, 0, 0, 0, 0, 2],
        [5, 4, 4, 4, 2, 2]]
DIFF = [[0, 1],
        [1, 0],
        [0, -1],
        [-1, 0]]

def solve
  qs = [
    {
      pos: [0, 0],
      pat: [[1, 1, 1],
            [1, 0, 0]],
    },
    {
      pos: [4, 0],
      pat: [[0, 2],
            [0, 2],
            [2, 2]],
    },
    {
      pos: [1, 1],
      pat: [[3, 3, 3],
            [0, 0, 3]],
    },
    {
      pos: [0, 2],
      pat: [[4, 4, 4]],
    },
    {
      pos: [0, 3],
      pat: [[5],
            [5],
            [5]],
    },
    {
      pos: [1, 3],
      pat: [[6, 6],
            [0, 6]],
    },
    {
      pos: [4, 3],
      pat: [[7, 7],
            [7, 0]],
    },
  ]

  board = BOARD.map(&:dup)
  checks = {}
  qs.each do |q|
    qx, qy = q[:pos]
    q[:pat].each_with_index do |t, py|
      t.each_with_index do |n, px|
        board[qy + py][qx + px] = n
      end
    end
  end
  key = board.map { |line| line.join(',') }.join('|')
  checks[key] = true

  queue = [[qs, []]]
  ans_size = nil

  until queue.empty?
    qs, ans = queue.shift
    board = BOARD.map(&:dup)
    qs.each do |q|
      qx, qy = q[:pos]
      q[:pat].each_with_index do |t, py|
        t.each_with_index do |n, px|
          board[qy + py][qx + px] = n unless n.zero?
        end
      end
    end

    if board == WANT
      pp ans
      break
    end
    unless ans_size == ans.size
      ans_size = ans.size
      pp ans_size
    end

    qs.each_with_index do |q, k|
      qx, qy = q[:pos]
      pat = q[:pat]
      sx, sy = pat[0].size, pat.size

      pat.each_with_index do |t, py|
        t.each_with_index do |n, px|
          board[qy + py][qx + px] = 0 unless n.zero?
        end
      end

      DIFF.each do |(dx, dy)|
        bx, by = qx + dx, qy + dy
        # p [k, [dx, dy], [bx, by]]
        if bx < 0 || by < 0 || bx + sx > board[0].size || by + sy > board.size
          # p ['範囲外']
          next
        end

        can_place = true
        pat.each_with_index do |t, py|
          break unless can_place
          t.each_with_index do |n, px|
            m = board.dig by + py, bx + px

            next if n.zero?
            next if m.zero?

            # p ['既にある', [bx, + px, by + py], n, m]
            can_place = false
            break
          end
        end

        next unless can_place

        pat.each_with_index do |t, py|
          t.each_with_index do |n, px|
            board[by + py][bx + px] = n unless n.zero?
          end
        end

        key = board.map { |line| line.join(',') }.join('|')
        unless checks[key]
          checks[key] = true
          new_qs = qs.dup
          new_q = q.dup
          new_q[:pos] = [bx, by]
          new_qs[k] = new_q
          queue.push [new_qs, ans + [[k + 1, [dx, dy]]]]
        else
          # p ['探索済']
        end

        pat.each_with_index do |t, py|
          t.each_with_index do |n, px|
            board[by + py][bx + px] = 0 unless n.zero?
          end
        end
      end

      pat.each_with_index do |t, py|
        t.each_with_index do |n, px|
          board[qy + py][qx + px] = n unless n.zero?
        end
      end
    end
  end
end

solve