Warnsdorff在Scala中自定义移动的算法

Question

我编写了一个程序来查找使用Warnsdorff算法覆盖棋盘所有平方所需的移动列表。 它非常适合 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
      }
    }
  }
}

Answer 1

来自维基百科

骑士被移动，以便它总是前进到骑士向前移动最少的广场

您的实现未考虑已访问的方块。它在空板上创建和排序可能的移动，但在算法移动时忘记更新它们。

当访问正方形时，您应该将其从可能的移动中删除，然后再次重新排序可能的移动