如何使用最小冲突启发式避免陷入8-queens的局部极小值

Question

我写了以下代码来解决n-queens问题：

(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个queens放置在彼此不会受到威胁的单元中？

要运行该程序：

(setf board (make-board 8))
(solve board 10)

其中10表示solve在原板上被召回的次数。

我没有包括我的函数，因为它们是不言而喻的，但如果它们会有帮助，我将很乐意包括它们。

Answer 1

我试图通过重新启动原来的板子来解决这个问题，但是不管我重启多少次，它似乎都不起作用，因为所有的皇后都卡在最小冲突的点上，即使它们仍然冲突

我认为这仅仅意味着你给出的初始位置根本不能被启发式方法“修复”。在这种情况下，你需要一个新的“种子”，你可以在所有8列中随机选择一行，然后这样做(如果它被证明是一个糟糕的种子)，直到你得到一个好的种子。

由于解空间是渐近增加的，因此在n*n板中，“好”的初始位置/种子越多，“n”越高。

下面是一个具有这些注意事项的Java类(主要是main和shuffle方法)：https://github.com/danielbmancini/JHTP8_JCP8_Sol._Comentadas/blob/master/7/src/EightQueensHeuristic.java

我希望这能对你有所帮助。如果我在任何方面都错了，欢迎批评。