我编写了以下代码来解决n皇后问题:
(defun solve (board max-steps)
(enforce-one-queen-per-column board)
(dotimes (step max-steps) ; repeat for a max amount of times,
(if (eql (get-threatened-queens board) 0) ; if we have solved the board, return it
(progn
(format t "Solved!")
(return board)
)
)
(let ((threatened-queens (get-threatened-queens board)) ; get all threatened queens
(queen nil))
(setf queen (nth (random (length threatened-queens)) threatened-queens)) ; choose random threatened queen
; find which row in its column where it would be least threatened
(let ((row-with-min-threats nil) ; (row_index, num_threats set to a high number)
(col (car queen))
(row (cdr queen)))
(format t "Dealing with threatened queen at (~A, ~A)...~%" col row)
(dotimes (i (array-dimension board 0)) ; for each row, find num of threats
(let ((num-threats (get-num-threats board col i)))
(print (car row-with-min-threats))
(format t "Checking (~A, ~A)~%" col i)
(format t "Threatened by ~A queens...~%" num-threats)
; if row-with-min-threats has not yet been initialized
; or if the row's threat is smaller than the tracked row with min threats
; take first row as min threat so far
(if (eql row-with-min-threats nil) ;
(setf row-with-min-threats (cons i num-threats))
(if (< num-threats (cdr row-with-min-threats)) ; if not first row and current min threats is smaller than tracked min
(setf row-with-min-threats (cons i num-threats))
(if (and (eql num-threats (cdr row-with-min-threats))
(eql (random 2) 1)) ; if current cell's & min cell's threats are equal, we randomly decide which cell to assign
(progn
(format t "Randomly chose (~A, ~A)...~%" col i)
(setf row-with-min-threats (cons i num-threats)))
)
)
)
)
)
(format t "Least threatened cell is (~A, ~A)...~%" col (car row-with-min-threats))
(if (not (eql row (car row-with-min-threats))) ; if its least threatened position isn't where it currently is
(progn
(setf (aref board (car row-with-min-threats) col) 1) ; move queen
(setf (aref board row col) 0)
(format t "Moved queen to (~A, ~A)...~%" col (car row-with-min-threats))
)
)
)
)
)
nil
)
我正在尝试解决8皇后问题。问题出在solve
函数中,但是我不确定自己做错了什么。由于我使用的是最小冲突启发式方法,因此我感觉自己陷入了局部最小值。我试图通过重新启动原始电路板的问题来解决此问题,但是无论我重新启动多少次,它似乎都无法正常工作,因为即使它们仍然存在冲突,但女王/王后都卡在最小冲突的位置上。我如何改进solve
才能成功地将8个皇后放在不会互相威胁的牢房中?
运行程序:
(setf board (make-board 8))
(solve board 10)
其中10代表solve
在原始板上被调用的次数。
我没有包含我的功能,因为它们是不言自明的,但是如果它们会有所帮助,我很乐意将它们包含在内。
我试图通过重新启动原始电路板来解决此问题,但是无论我重启多少次,它似乎都无法正常工作,因为皇后都卡在了最小冲突的位置,即使它们仍然冲突
我相信这只是意味着您无法通过启发式方法来“修复”您给定的初始位置。在这种情况下,您需要一个新的“种子”,您可以通过在所有8列中随机选择一行,然后这样做(如果事实证明它是不好的种子),直到获得一个好的“种子”。由于解空间渐近增加,因此在n * n板上,“ n”越高,“好的”初始位置/种子越多。
这里是一个具有以下考虑因素的Java类(主要在main和shuffle方法中:https://github.com/danielbmancini/JHTP8_JCP8_Sol._Comentadas/blob/master/7/src/EightQueensHeuristic.java
我希望这对您有帮助。如果我有任何错误,欢迎提出批评。