我试图通过随机填充棋盘来解决方案中的 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 语句检查棋盘上的所有皇后是否都已移动。如果有，则检查是否存在任何冲突（如果没有冲突，(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 " ")
))
编辑：我在想问题可能是我的（解决）函数遍历列的方式。如果我总是按递增顺序排列，如果前几列的冲突为零，但在不能成为合法解决方案的地方，那么剩余的列将移动到冲突最少但绝不为零的地方。