Алгоритм Варнсдорфа для настраиваемого перемещения в Scala

Я написал программу для поиска списка ходов, необходимых для покрытия всего квадрата шахматной доски, с использованием алгоритма Варнсдорфа. он отлично работает для платы 7x7, но не работает для таких плат, как 8x8, 10x10 или 16x16. Он работает долго. Ниже приведен код. Укажите, пожалуйста, в чем я ошибаюсь.

object PawnTourMain {

  def main(args: Array[ String ]): Unit = {

    val kt = PawnTour(7)
    kt.findTour(0, 1, 0)
    kt.printSolution        
  }

  class PawnTour(size: Int, board: Array[ Array[ Int ] ], possibleMoves: Array[ Array[ Array[ Point ] ] ]) {

    val UNUSED = -1

    def findTour(x: Int, y: Int, current: Int): Boolean = {
      if (board(x)(y) != UNUSED) return false
      //Mark current position as 'current'
      board(x)(y) = current
      if (current == size * size - 1) { //done :)
        return true
      }
      for (d <- possibleMoves(x)(y)) {
        if (findTour(d.x, d.y, current + 1)) return true
      }
      //if we are here, all our options ran out :(
      //reset the current cell and return false
      board(x)(y) = UNUSED
      false
    }

    def printSolution: Unit = {
      board foreach {
        row =>
          row foreach (number => print(number + " ")); println
      }
    }    
  }

  case class Point(x: Int, y: Int)

  object PawnTour {

    val DIRECTIONS = Array(Point(3, 0), Point(-3, 0), Point(2, -2), Point(2, 2), Point(0, 3), Point(0, -3), Point(-2, -2), Point(2, 2))

    def apply(n: Int): PawnTour = {
      val board = Array.fill[ Int ](n, n)(-1)
      val possibleMoves = Array.tabulate(n, n) { (x, y) =>
        DIRECTIONS.flatMap { d =>
          val nx = x + d.x
          val ny = y + d.y
          if ((nx >= 0 && nx < n) && (ny >= 0 && ny < n)) Option(Point(nx, ny)) else None
        }
      }

      var x = 0
      while (x < n) {
        var y = 0
        while (y < n) {
          val moves: Array[ Point ] = possibleMoves(x)(y)
          moves.sortBy((o1: Point) => possibleMoves(o1.x)(o1.y).size)
          y += 1
          println(moves.toList)
        }
        x += 1
      }
      new PawnTour(n, board, possibleMoves)
    }

    def printSolution(array: Array[ Array[ Int ] ]): Unit = {
      array foreach {
        row =>
          row foreach (number => print(number + " ")); println
      }
    }
  }
}

@JoelBerkeley "но не работает для платы типа 8x8, 10x10" -> скорее всего, нет.

301_Moved_Permanently 09.08.2018 11:18

@JoelBerkeley Нет, потому что OP специально просит исправить ошибку для 8, 10 и 16 в квадрате. Это конкретная проблема программирования, поэтому с этой точки зрения она идеально подходит для SO. Однако OP не смог предоставить MCVE.

Mast 09.08.2018 11:19

@JoelBerkeley один из выходных данных может быть: выход в формате 10x10 mcve 0 57 15 1 58 16 2 59 17 3 25 41 12 26 42 11 27 43 10 28 14 69 91 76 70 90 75 99 89 45 93 56 72 94 86 78 95 60 18 4 24 40 13 80 74 98 88 44 9 29 51 68 92 77 71 82 85 64 32 46 36 55 73 97 87 79 96 61 19 5 23 39 52 81 84 63 31 83 8 30 50 67 35 49 66 34 48 65 33 47 37 54 22 38 53 21 7 62 20 6 код запуска для 7x7 Выход: 0 36 29 5 35 28 48 21 16 11 22 17 12 23 30 6 44 14 9 43 34 1 37 18 4 40 27 47 20 15 10 25 45 13 24 31 7 41 32 8 42 33 2 38 19 3 39 26 46, если вы запустите код для 7x7

shishir kumar 09.08.2018 12:11

@JoelBerkeley это не относится к обзору кода

shishir kumar 09.08.2018 12:15
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
4
109
1

Ответы 1

Из Википедии

The knight is moved so that it always proceeds to the square from which the knight will have the fewest onward moves

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

Когда квадрат посещается, вы должны удалить его из возможных ходов, а затем снова изменить порядок возможных ходов.

Я обновляю board(x)(y) = current

shishir kumar 09.08.2018 15:36

Я говорю о possibleMoves - он конструируется только один раз для пустой платы, но должен пересчитываться каждый раз при смене платы.

Nazarii Bardiuk 09.08.2018 15:46

Другие вопросы по теме