Схема - Решение NQueens с использованием метода восхождения на холм / минимального конфликта

Я пытаюсь решить проблему N-ферзей в схеме, случайным образом заполняя доску ферзями так, чтобы никакие два ферзя не находились в одной строке или столбце, а затем перемещая ферзей в своем столбце в ряд, который атакуется наименьшим числом королев.

Мой алгоритм работает для доски любого размера меньше 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 " ")
    ))

РЕДАКТИРОВАТЬ: я думаю, что, возможно, проблема в том, как моя (решающая) функция выполняет итерацию по столбцам. Если я всегда буду идти в порядке возрастания, если первые несколько столбцов не имеют конфликта, но находятся в местах, которые не могут быть законным решением, тогда оставшиеся столбцы будут перемещены в места наименьшего, но никогда не нулевого конфликта.