Scheme - Solving NQueens using hill-climbing/min-conflict method

Question

I'm trying to solve the N-Queens problem in Scheme by randomly populating the board with queens such that no two queens are on the same row or column, then moving queens within their column to the row that is being attacked by the fewest number of queens.

My algorithm works for any size board less than 6. If a board size of 6 or greater is used as a parameter, then the program appears to recurse infinitely.

I am going to add all the code, but here's the part where I believe the infinite recursion occurs:

(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))
        )
      ))

The first if statement checks to see if all the queens on the board have been moved. If they have it checks to see if there are any conflicts ((move i) returns 0 if there are no conflicts). If there are conflicts, then a flag is raised and the program will continue moving queens.

So here's the problem. The puzzle is either solved in the first pass, or not at all. If the board is legal after the first pass, obviously there are no problems and everything is fine. However, if it is not, then the same board just keeps getting tried over and over. I know this because of the (display board) checks in the code.

I assume the code doesn't work for a board size greater than 6, because that's the point where it's unlikely that the puzzle will be solved in the first pass. I tried adding a line where a new random board would be created, but at that point the run-time is just abysmal and it doesn't help me.

Below is the code for the program, if you have any questions, feel free to ask.

#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 " ")
    ))

EDIT: I'm thinking that maybe the problem is the way my (solve) function iterates through the columns. If I always go in increasing order, if the first few columns have zero conflict, but are in places that can't be a legal solution, then the remaining columns will get moved to places of least, but never zero, conflict.

Answer 1

I solved this by placing the queens randomly during each iteration instead of progressing in the same sequential order.