Я написал программу для поиска списка ходов, необходимых для покрытия всего квадрата шахматной доски, с использованием алгоритма Варнсдорфа. он отлично работает для платы 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 Нет, потому что OP специально просит исправить ошибку для 8, 10 и 16 в квадрате. Это конкретная проблема программирования, поэтому с этой точки зрения она идеально подходит для SO. Однако OP не смог предоставить MCVE.
@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
@JoelBerkeley это не относится к обзору кода
Из Википедии
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
Я говорю о possibleMoves
- он конструируется только один раз для пустой платы, но должен пересчитываться каждый раз при смене платы.
@JoelBerkeley "но не работает для платы типа 8x8, 10x10" -> скорее всего, нет.