方案 - 使用爬山/最小冲突方法解决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 语句检查董事会上的所有皇后是否已移动。 如果他们有它，请检查是否有任何冲突(如果没有冲突，则返回 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 " ")
    ))

编辑：我想也许问题出在我的(解决(函数遍历列的方式。 如果我总是按递增的顺序排列，如果前几列的冲突为零，但位于无法成为合法解决方案的地方，那么其余列将被移动到冲突最少但永远不会为零的地方。

Answer 1

我通过在每次迭代中随机放置皇后而不是以相同的顺序进行来解决此问题。