基于爬山/最小冲突法的NQueens方案求解

Question

我正在尝试解决Scheme中的N-Queens问题，方法是在棋盘上随机填充皇后，使得没有两个皇后在同一行或同一列上，然后将列中的皇后移到受到皇后数量最少攻击的行。

我的算法适用于任何尺寸小于6的电路板。如果使用6或更大的电路板尺寸作为参数，则程序似乎无限递归。

我将添加所有代码，但这里是我认为无限递归发生的部分：

(define (solve col)
  (if (= col (vector-length board))
      (begin
        (do ((i 0 (+ i 1))) ((>= i (vector-length board)))
          (if (not (= (move i) 0))
             (set! legal #f))
          )  
        (if (eqv? legal #t)
            (begin
              (display steps)
              (newline)
              (display board)
             )
            (begin
              ;(random-fill (build-list (vector-length board) add)) ;
              (display board)
              (solve 0))
          )
        )
      (begin
        (move col)
        (solve (+ col 1))
        )
      ))

第一个if语句检查板上的所有queens是否都已被移动。如果有，它会检查是否有冲突((move i)如果没有冲突，则返回0)。如果存在冲突，则会发出一个标志，程序将继续移动皇后。

这就是问题所在。这个难题要么在第一个过程中就解决了，要么根本不解决。如果董事会在第一次通过后是合法的，显然没有问题，一切都很好。然而，如果不是这样，那么同一个板子就会不断地被反复试用。我知道这是因为代码中的(显示板)检查。

我假设代码不适用于大于6的棋盘，因为在这一点上，拼图不太可能在第一次通过中得到解决。我试着添加一行代码，在那里创建一个新的随机板子，但是在这一点上，运行时非常糟糕，对我没有帮助。

下面是程序的代码，如果你有任何问题，请随时提问。

#lang swindle
(define steps 0)
(define board (make-vector 0))
(define legal #t)

;function to be called for hill-climbing method of solving problem
(define (nq-mc size)
  (set! steps 0)
  (set! board (make-vector size))
  (random-fill (build-list size add))
  (set! legal #t)
  (solve 0)
  ;writes solution to txt file
  (define out-board (open-output-file "board-mc.txt" 'replace))
  (iter-write board out-board)
  (close-output-port out-board)
  )

;function for filling board randomly, no queens will be on same row or col
(define (random-fill list)
  (if (eqv? list '())
      (display board)
  (let ([var (random-element list)])
    (vector-set! board (- (length list) 1) var)
    (random-fill (remv var list))
    )
  ))

;helper function for randomization, retrieves random number from legal options
(define (random-element list)
  (list-ref list (random (length list))))

(define (solve col)
  (if (= col (vector-length board))
      (begin
        (do ((i 0 (+ i 1))) ((>= i (vector-length board)))
          (if (not (= (move i) 0))
              (set! legal #f))
          )
        (if (eqv? legal #t)
            (begin
              (display steps)
              (newline)
              (display board)
              )
            (begin
              ;(random-fill (build-list (vector-length board) add))
              (display board)
              (solve 0))
          )
        )
      (begin
        (move col)
        (solve (+ col 1))
        )
      ))


;moves a queen to location of least-conflict
(define (move col)
  (let ((conf-vec (make-vector (vector-length board))))
    (do ((i 0 (+ i 1))) ((= i (vector-length board)))
      (vector-set! conf-vec i (conflicts i col))
      )
    (let ((min (vector-ref conf-vec 0)))
      (do ((i 0 (+ i 1))) ((= i (vector-length board)))
        (cond [(< (vector-ref conf-vec i) (vector-ref conf-vec min))
               (set! min i)]
              [(= (vector-ref conf-vec i) (vector-ref conf-vec min))
               (if (not (eqv? (vector-ref board col) i))
                   (if (= (random 2) 0)
                       (set! min i)
                       )
                   )]
              )
        )
      (vector-set! board col min)
      (vector-ref conf-vec min))
    ))

;function for determining how many queens are attacking a space
(define (conflicts row col)
  (define conflict 0)
  (do ((i 0 (+ i 1))) ((= i (vector-length board)))
    (set! steps (+ steps 1))
    (cond [(= i col) (+ conflict 0)]
          [(= (vector-ref board i) row)
           (set! conflict (+ conflict 1))]
          [(= (abs (- i col)) (abs (- (vector-ref board i) row)))
           (set! conflict (+ conflict 1))]
          )
    )
  conflict)

;helper function for writing output to file in a easily machine-readable fashion
(define (iter-write vector out-port)
  (do ((i 0 (+ i 1))) ((= i (vector-length board)))
    (write (vector-ref vector i) out-port)
    (fprintf out-port " ")
    ))

编辑:我认为问题可能出在我的(solve)函数迭代列的方式上。如果我总是以递增的顺序进行，如果前几列没有冲突，但是位于不能合法解决的地方，那么剩下的列将被移到冲突最少的地方，但永远不会是零冲突的地方。

Answer 1

我解决这个问题的方法是在每次迭代中随机放置皇后，而不是按相同的顺序进行。