I wrote the following code:

```
(defun make-board (num-queens)
(setf board (make-array '(8 8))) ;; make empty board
(dotimes (i num-queens) ;; for each of 8 queens,
(loop ; loop until we generate a random coordinate that doesn't already have a queen in it
(setf x (random 8) y (random 8))
(when (not (eql (aref board x y) 1))
(return))
)
(setf (aref board x y) 1) ;; add queen to this coordinate
) board ;; return board
)
(defun out-of-bounds (board x y)
(or (>= x (array-dimension board 0))
(>= y (array-dimension board 1))
(< y 0)
(< x 0)
)
)
(defun is-queen (board x y)
(eql (aref board y x) 1)
)
(defun search-row (board x y)
(let ((num-threats 0))
(dotimes (a (array-dimension board 1)) ;; loop over the columns in that row
(if (and (not (eql x a)) (is-queen board a y)) ;; if the cell is a queen and not the same queen
(progn
;(format t "(~A, ~A) is a queen in the same row~%" a y)
(incf num-threats 1) ;; immediately return true - there is another queen in this row
)
)
)
num-threats
)
)
(defun search-column (board x y)
(let ((num-threats 0))
(dotimes (b (array-dimension board 0)) ; loop over the rows in that column
(if (and (not (eql y b)) (is-queen board x b)) ; if the cell contains a queen
(progn
;(format t "(~A, ~A) is a queen in the same column~%" x b)
(incf num-threats 1) ; immediately return true - there is a queen in this row
)
)
)
num-threats
)
)
(defun search-up-left-diagonal (board x y)
(let ((num-threats 0))
;(format t "Searching up the left diagonal from (~A, ~A)...~%" x y)
(do ((a (- x 1) (- a 1))
(b (- y 1) (- b 1)))
((out-of-bounds board a b) nil) ; end clause
(if (is-queen board a b) ;; if current coordinate holds queen
(progn
;(format t "(~A, ~A) is a queen in the same diagonal~%" a b) ;; print info
(incf num-threats 1) ;; return true
)
)
)
num-threats
)
)
(defun search-up-right-diagonal (board x y)
(let ((num-threats 0))
;(format t "Searching up the right diagonal from (~A, ~A)...~%" x y)
(do ((a (+ x 1) (+ a 1))
(b (- y 1) (- b 1)))
((out-of-bounds board a b) nil) ; end clause
(if (is-queen board a b) ;; if current coordinate holds queen
(progn
;(format t "(~A, ~A) is a queen in the same diagonal~%" a b) ;; print info
(incf num-threats 1) ;; return true
)
)
)
num-threats
)
)
(defun search-down-left-diagonal (board x y)
;(format t "Searching down the left diagonal from (~A, ~A)...~%" x y)
(let ((num-threats 0))
(do ((a (- x 1) (- a 1))
(b (+ y 1) (+ b 1)))
((out-of-bounds board a b) nil) ; end clause
(if (is-queen board a b) ;; if current coordinate holds queen
(progn
;(format t "(~A, ~A) is a queen in the same diagonal~%" a b) ;; print info
(incf num-threats 1)
)
)
)
num-threats
)
)
(defun search-down-right-diagonal (board x y)
(let ((num-threats 0))
;(format t "Searching down the right diagonal from (~A, ~A)...~%" x y)
(do ((a (+ x 1) (+ a 1))
(b (+ y 1) (+ b 1)))
((out-of-bounds board a b) nil) ; end clause
(if (is-queen board a b) ;; if current coordinate holds queen
(progn
;(format t "(~A, ~A) is a queen in the same diagonal~%" a b) ;; print info
(incf num-threats 1) ;; return true
)
)
)
num-threats
)
)
(defun search-diagonals (board x y)
(+ (search-up-left-diagonal board x y)
(search-up-right-diagonal board x y)
(search-down-left-diagonal board x y)
(search-down-right-diagonal board x y)
)
)
(defun get-num-threats (board x y)
(+ (search-row board x y)
(search-column board x y)
(search-diagonals board x y))
)
(defun is-threatened (board x y)
(if (> (get-num-threats board x y) 0)
t
nil
)
)
(defun get-threatened-queens (board)
(let ((threatened-queens '()))
(dotimes (x (array-dimension board 0)) ; loop over columns
(dotimes (y (array-dimension board 1)) ; loop over rows
(if (and (is-queen board x y) (is-threatened board x y))
(progn
;(format t "(~A, ~A) is a threatened queen~%" x y)
(setf threatened-queens (cons (cons x y) threatened-queens))
)
)
)
)
threatened-queens ; return total (as last expression in let)
)
)
(defun enforce-one-queen-per-column (board)
(dotimes (col (array-dimension board 1)) ; loop over columns (going back to 1st column at the end)
(let ((has-queen nil)) ; to track whether the column has one queen
(dotimes (row (array-dimension board 0)) ; loop over cells
(if (eql (aref board row col) 1) ; if cell contains a queen
(if (not has-queen) ; if we have no queen in this column yet, track this queen
(setf has-queen t)
(progn ; otherwise, remove queen
(setf (aref board row col) 0)
)
)
)
)
(if (not has-queen) ; if this column had no queens, randomly place one
(setf (aref board (random 8) col) 1)
)
)
)
)
(defun solve (orig-board max-steps)
(setf board orig-board)
(enforce-one-queen-per-column board)
(dotimes (step 50) ; 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 num-threats)
; if the row's threat is smaller than the tracked row with min threats
(if (or (not row-with-min-threats) ; if row-with-min-threats has not yet been initialized, assign this row
(< num-threats (cdr row-with-min-threats)))
(setf row-with-min-threats (cons i num-threats))
)
; if current cell's & min cell's threats are equal, we randomly decide which cell to assign
(if (and (eql num-threats (cdr row-with-min-threats))
(eql (random 2) 1))
(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))
)
)
)
)
)
;(decf max-steps 1)
(if (eql (get-threatened-queens board) 0) ; if we have solved the board, return
(progn
(format t "Solved!")
board
)
(if (and (> max-steps 1))
(progn
(format t "Stuck.")
(print board)
(solve orig-board (- max-steps 1)) ; we may have gotten stuck in a local minima
)
)
)
board
)
```

I'm trying to solve the 8-lady problem. I think the problem lies in the `solve`

Function, but I'm not sure what I'm doing wrong. Since I use the Min Conflicts heuristic, I feel like I'm stuck in a local minima. I tried to overcome this by restarting the problem with the original board, but it does not seem to work. How can I improve? `solve`

to place the 8 queens successfully in cells where they do not threaten each other?

To run the program:

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

where 10 represents the number of times `solve`

is recalled on the original panel.