1
\$\begingroup\$

I am using following method to solve N-queens problem for all possible solutions for a board. It seems to be smaller as well as faster than many commonly mentioned method. Also, since it is tail-recursive, it should not create any memory problem on longer runs or with larger board sizes.

I tried to implement the method that I was manually trying:

Put a queen on first column (from below to up) of first index (from left to right). Go to next column to the right (number indicated by I); try putting queen on that column from below upwards (value indicated by V); If non-attacking position found, goto next column; If all columns tried, go to previous column and advance queen on that column to find new non-attacking position. If able to place queen in last column, a solution is found. When queen in first column has to be advanced beyond the board, all possible positions have been tested and searching can end.

The code also rotates the board and reverses these solutions to get a total of 4 solutions from each solution found.

The code is:

; SET BOARD WIDTH:
(define N 5)
(define Boardlist (build-list N (λ (x) 1)))
(define I 0) ; I for index (horizontal, column number)
(define V 0) ; V for vertical position of queen in that column.

; counter for solutions found: 
(define count 0)

; get sublist: both start and end indexes are included in sublist; 
(define (rnsublist sentList start (end (length sentList)))
  (for/list ((x sentList)(i (length sentList))
                         #:when (> i (sub1 start))
                         #:break(> i end))
    x))

; Following function returns true if queens are in attacking position: 
(define (check-board bd) 
  (define res #f)
  (if (check-duplicates bd)  #t 
      (begin
        (for ((r1 (length bd))
              #:break (equal? res #t))
          (for ((r2 (range (add1 r1) (length bd)))
                #:break (equal? res #t))
            (when (= (abs (- r1 r2))
                     (abs(- (list-ref bd r1)
                            (list-ref bd r2))))
              (set! res #t))))
        res)))

; get board rotated by 90 degrees: 
(define (rotateBoard ll)
  (set! ll (map sub1 ll))
  (define outl (build-list (length ll) values))
  (for ((i (length ll)))
    (set! outl (list-set outl (list-ref ll i) (sub1(-(length ll) i)))))
  (map add1 outl))

; Go to next column: 
; If already at 8th column, declare solution found: 
(define (incI)
  (set! I (add1 I))
  (if (= I N)
      (begin 
        ; (print "-------------Solution found...")  
        (set! count (add1 count))
        (printf "~a. " count) 
        (println "A solution, same rotated and their reverse: ")
        (let ((rot (rotateBoard Boardlist)))
          (println Boardlist)
          (println rot)                    ; rotated board is also a solution
          (println (reverse Boardlist))    ; reversed board is also a solution
          (println (reverse rot)))
        (set! Boardlist (list-set Boardlist (sub1 I) 0))
        (set! I (- I 2))
        (set! V (add1 (list-ref Boardlist I)))
        (incV))
      (begin
        (set! V 1)
        (set! Boardlist (list-set Boardlist I V)))))

; Advance queen in current column
; if already at 8th position, goto previous column and try higher positions of queen there.
(define (incV)
  (if (> (add1 V) N)
      (begin
        (set! Boardlist (list-set Boardlist I 0))
        (set! I (sub1 I))
        (when (< I 0)
          (exit))  ; ALL SOLUTIONS TESTED; ENDING; 
        (set! V (list-ref Boardlist I))
        (incV))
      (begin 
        (set! V (add1 V))
        (set! Boardlist (list-set Boardlist I V)))))

; START SEARCHING: 
(let loop ()
  (if (check-board (rnsublist Boardlist 0 I)) ; Are queens attacking each other?
      (incV)  ; If queens attacking, advance queen of rightmost column;
      (incI)) ; If queens not attacking, go to next column; 
  (loop))

Initial output for N=25 (25x25 board) is:

1. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 19 21 24 20 25 23 6 8 10 7 14 16 18 12 17 22)
'(25 22 24 21 23 10 7 9 20 8 19 3 18 6 17 5 2 4 16 13 15 1 11 14 12)
'(22 17 12 18 16 14 7 10 8 6 23 25 20 24 21 19 15 13 11 9 4 2 5 3 1)
'(12 14 11 1 15 13 16 4 2 5 17 6 18 3 19 8 20 9 7 10 23 21 24 22 25)
2. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 19 25 22 24 21 23 6 10 7 14 12 18 8 17 20 16)
'(25 22 24 21 23 10 8 4 20 9 19 6 18 7 17 1 3 5 16 2 12 14 11 13 15)
'(16 20 17 8 18 12 14 7 10 6 23 21 24 22 25 19 15 13 11 9 4 2 5 3 1)
'(15 13 11 14 12 2 16 5 3 1 17 7 18 6 19 9 20 4 8 10 23 21 24 22 25)
3. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 19 25 23 21 24 22 6 10 7 14 12 18 8 17 20 16)
'(25 22 24 21 23 10 8 4 20 9 19 6 18 7 17 1 3 5 16 2 13 11 14 12 15)
'(16 20 17 8 18 12 14 7 10 6 22 24 21 23 25 19 15 13 11 9 4 2 5 3 1)
'(15 12 14 11 13 2 16 5 3 1 17 7 18 6 19 9 20 4 8 10 23 21 24 22 25)
4. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 21 19 24 22 6 25 23 10 7 14 8 17 12 20 18 16)
'(25 22 24 21 23 12 8 6 20 9 19 4 18 7 17 1 5 2 15 3 16 13 10 14 11)
'(16 18 20 12 17 8 14 7 10 23 25 6 22 24 19 21 15 13 11 9 4 2 5 3 1)
'(11 14 10 13 16 3 15 2 5 1 17 7 18 4 19 9 20 6 8 12 23 21 24 22 25)
5. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 23 20 22 25 21 7 24 12 8 6 16 18 10 14 17 19)
'(25 22 24 21 23 7 11 8 20 4 19 9 18 3 17 6 2 5 1 15 12 14 16 10 13)
'(19 17 14 10 18 16 6 8 12 24 7 21 25 22 20 23 15 13 11 9 4 2 5 3 1)
'(13 10 16 14 12 15 1 5 2 6 17 3 18 9 19 4 20 8 11 7 23 21 24 22 25)
6. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 16 20 23 25 22 8 21 24 6 15 10 12 7 17 19 14 18)
'(25 22 24 21 23 9 5 12 20 7 19 6 18 2 8 17 4 1 3 16 11 13 15 10 14)
'(18 14 19 17 7 12 10 15 6 24 21 8 22 25 23 20 16 13 11 9 4 2 5 3 1)
'(14 10 15 13 11 16 3 1 4 17 8 2 18 6 19 7 20 12 5 9 23 21 24 22 25)
7. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 16 21 19 22 25 6 24 7 23 8 14 17 15 10 12 20 18)
'(25 22 24 21 23 12 10 8 20 4 19 3 18 7 5 17 6 1 15 2 16 14 9 11 13)
'(18 20 12 10 15 17 14 8 23 7 24 6 25 22 19 21 16 13 11 9 4 2 5 3 1)
'(13 11 9 14 16 2 15 1 6 17 5 7 18 3 19 4 20 8 10 12 23 21 24 22 25)
8. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 16 21 19 24 7 23 25 22 6 15 10 8 14 12 18 20 17)
'(25 22 24 21 23 9 13 6 20 7 19 4 18 5 8 17 1 3 15 2 16 10 12 14 11)
'(17 20 18 12 14 8 10 15 6 22 25 23 7 24 19 21 16 13 11 9 4 2 5 3 1)
'(11 14 12 10 16 2 15 3 1 17 8 5 18 4 19 7 20 6 13 9 23 21 24 22 25)
9. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 16 21 19 25 23 8 24 22 6 15 10 7 14 12 18 20 17)
'(25 22 24 21 23 9 6 12 20 7 19 4 18 5 8 17 1 3 15 2 16 10 13 11 14)
'(17 20 18 12 14 7 10 15 6 22 24 8 23 25 19 21 16 13 11 9 4 2 5 3 1)
'(14 11 13 10 16 2 15 3 1 17 8 5 18 4 19 7 20 12 6 9 23 21 24 22 25)
10. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 16 21 25 20 22 24 7 10 23 6 14 17 8 12 19 15 18)
'(25 22 24 21 23 8 11 5 20 10 19 4 18 7 2 17 6 1 3 14 16 13 9 12 15)
'(18 15 19 12 8 17 14 6 23 10 7 24 22 20 25 21 16 13 11 9 4 2 5 3 1)
'(15 12 9 13 16 14 3 1 6 17 2 7 18 4 19 10 20 5 11 8 23 21 24 22 25)
^Cuser break

Initial solution for N=31 (31x31 board):

1. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 6 18 23 26 28 31 25 27 30 7 17 29 14 10 8 20 12 16 19 22 24 21)
'(31 28 30 27 29 22 13 8 26 9 25 6 24 10 23 5 12 21 4 7 1 3 20 2 16 19 15 18 11 14 17)
'(21 24 22 19 16 12 20 8 10 14 29 17 7 30 27 25 31 28 26 23 18 6 15 13 11 9 4 2 5 3 1)
'(17 14 11 18 15 19 16 2 20 3 1 7 4 21 12 5 23 10 24 6 25 9 26 8 13 22 29 27 30 28 31)
2. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 6 18 23 26 30 27 25 31 28 7 17 29 14 10 8 20 12 16 19 22 24 21)
'(31 28 30 27 29 22 13 8 26 9 25 6 24 10 23 5 12 21 4 7 1 3 20 2 16 19 17 14 11 18 15)
'(21 24 22 19 16 12 20 8 10 14 29 17 7 28 31 25 27 30 26 23 18 6 15 13 11 9 4 2 5 3 1)
'(15 18 11 14 17 19 16 2 20 3 1 7 4 21 12 5 23 10 24 6 25 9 26 8 13 22 29 27 30 28 31)
3. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 6 18 24 26 28 31 25 27 29 7 17 14 30 10 8 20 12 16 22 19 21 23)
'(31 28 30 27 29 22 13 8 26 9 25 6 24 11 23 5 12 21 3 7 2 4 1 20 16 19 15 18 14 10 17)
'(23 21 19 22 16 12 20 8 10 30 14 17 7 29 27 25 31 28 26 24 18 6 15 13 11 9 4 2 5 3 1)
'(17 10 14 18 15 19 16 20 1 4 2 7 3 21 12 5 23 11 24 6 25 9 26 8 13 22 29 27 30 28 31)
4. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 6 18 24 26 28 31 25 27 29 12 17 7 30 10 8 20 14 16 22 19 21 23)
'(31 28 30 27 29 22 11 8 26 9 25 13 24 6 23 5 12 21 3 7 2 4 1 20 16 19 15 18 14 10 17)
'(23 21 19 22 16 14 20 8 10 30 7 17 12 29 27 25 31 28 26 24 18 6 15 13 11 9 4 2 5 3 1)
'(17 10 14 18 15 19 16 20 1 4 2 7 3 21 12 5 23 6 24 13 25 9 26 8 11 22 29 27 30 28 31)
5. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 6 18 24 26 30 23 27 31 28 8 29 12 19 7 10 17 14 20 22 16 25 21)
'(31 28 30 27 29 22 9 13 26 8 25 11 24 6 23 3 7 21 10 5 1 4 17 20 2 19 16 14 12 18 15)
'(21 25 16 22 20 14 17 10 7 19 12 29 8 28 31 27 23 30 26 24 18 6 15 13 11 9 4 2 5 3 1)
'(15 18 12 14 16 19 2 20 17 4 1 5 10 21 7 3 23 6 24 11 25 8 26 13 9 22 29 27 30 28 31)
6. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 6 18 24 27 29 23 25 28 31 7 30 14 17 8 10 12 16 21 19 26 22 20)
'(31 28 30 27 29 22 13 9 26 8 25 7 24 11 23 6 10 21 4 1 5 2 17 20 16 3 19 15 18 12 14)
'(20 22 26 19 21 16 12 10 8 17 14 30 7 31 28 25 23 29 27 24 18 6 15 13 11 9 4 2 5 3 1)
'(14 12 18 15 19 3 16 20 17 2 5 1 4 21 10 6 23 11 24 7 25 8 26 9 13 22 29 27 30 28 31)
7. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 6 18 24 27 30 23 29 26 28 8 31 14 17 7 10 12 16 21 25 20 22 19)
'(31 28 30 27 29 22 9 13 26 8 25 7 24 11 23 6 10 21 1 3 5 2 17 20 4 15 19 14 16 18 12)
'(19 22 20 25 21 16 12 10 7 17 14 31 8 28 26 29 23 30 27 24 18 6 15 13 11 9 4 2 5 3 1)
'(12 18 16 14 19 15 4 20 17 2 5 3 1 21 10 6 23 11 24 7 25 8 26 13 9 22 29 27 30 28 31)
8. "A solution, same rotated and their reverse: "
'(1 3 5 2 4 9 11 13 15 6 18 24 28 23 29 27 25 31 7 30 14 8 10 16 22 20 12 17 19 21 26)
'(31 28 30 27 29 22 13 10 26 9 25 5 24 11 23 8 4 21 3 6 2 7 18 20 15 1 16 19 17 12 14)
'(26 21 19 17 12 20 22 16 10 8 14 30 7 31 25 27 29 23 28 24 18 6 15 13 11 9 4 2 5 3 1)
'(14 12 17 19 16 1 15 20 18 7 2 6 3 21 4 8 23 11 24 5 25 9 26 10 13 22 29 27 30 28 31)

Are there any bugs in this code and how can it be optimized? Thanks for your review.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.