## N-Queens

### June 11, 2010

Here is our solution:

```(define (queens n)   (let loop ((qs (range n 0)) (xs '()) (bs '()))     (if (null? qs)         (if (pair? xs) '() (list bs))         (append           (if (not (safe? (car qs) 1 bs)) '()             (loop (append (cdr qs) xs) '() (cons (car qs) bs)))           (loop (cdr qs) (cons (car qs) xs) bs)))))```

We build up the board one column at a time, placing the next queen so that it doesn’t attack any queens already on the board. `Qs` is the list of queens to be placed, `xs` is a list of queens that failed to place on the current board, and `bs` is the current board.

`Safe?` checks the diagonals; there is no need to check columns, since the algorithm places them one after the other, and there is no need to check rows because the list of queens is established at the beginning of the run:

```(define (safe? row offset board)   (or (null? board)       (and (not (= (+ row offset) (car board)))            (not (= (- row offset) (car board)))            (safe? row (+ offset 1) (cdr board)))))```

Here’s an example:

```> (length (queens 8)) 92 > (queens 5) ((2 4 1 3 5) (3 1 4 2 5) (1 3 5 2 4) (2 5 3 1 4) (5 2 4 1 3)   (1 4 2 5 3) (5 3 1 4 2) (4 1 3 5 2) (4 2 5 3 1) (3 5 2 4 1))```

We used `range` from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/BL9RmfPM.

Pages: 1 2

### 12 Responses to “N-Queens”

1. Remco Niemeijer said

```import Data.List

queens :: Int -> [[Int]]
queens n = filter (safe . zip [1..]) \$ permutations [1..n]

safe :: [(Int, Int)] -> Bool
safe []     = True
safe (x:xs) = all (safe' x) xs && safe xs where
safe' (x1,y1) (x2,y2) = x1+y1 /= x2+y2 && x1-y1 /= x2-y2
```
2. [...] Praxis – N-Queens By Remco Niemeijer In today’s Programming Praxis we have to solve the classic n-queens problem. The provided Scheme solution has [...]

3. I was trying to make a version that printed and counted, and would fit in 4 lines so you could use it as a .signature file. Didn’t quite succeed, mostly because I need to include to get printf, but here’s where I got it.

```#include <stdio.h>
int t,i,j,b[8],r;c(){r=1;for(i=0;i<7;i++)for(j=i+1;j<8;j++)r&=(b[i]-b[j]&&abs(i
-j)!=abs(b[i]-b[j]));return r;}p(){for(i=0;i<8;i++){for(j=0;j<8;j++)putchar(
" Q"[j==b[i]]);puts("");}puts("");t++;}s(n){int i;if(n--){for(i=8;i;){b[n]=--i;
s(n);}}else if(c(b))p(b);}main(){s(8);printf("%d solutions.\n",t);}
```
4. N = 8

def valid? stack
q2 = stack.length – 1
(0..stack.length-2).each do |q1|
return false if stack[q1] == stack[q2] ||
(q1-q2).abs == (stack[q1]-stack[q2]).abs
end
end

def queens stack, n
if n == N
puts “[ #{stack.join(', ')} ]”
else
(1..N).each do |rank|
stack.push(rank)
queens(stack, n+1) if valid?(stack)
stack.pop
end
end
end

queens [], 0

5. slabounty said

Here’s a ruby version (commented at http://steamcode.blogspot.com/2010/06/n-queens-problem-in-ruby.html)

```class Board

def initialize(n)
@n = n
@board = Array.new(n)
@board.map! { Array.new(n, "b") }
end

def print_board
puts "Board:"
@board.each_index do |row|
@board.each_index do |col|
end
puts
end
end

def safe_row(suggested_row)
0.upto(@n-1) do |col|
return false if @board[suggested_row][col] == "Q"
end

return true
end

def safe_col(suggested_col)
0.upto(@n-1) do |row|
return false if @board[row][suggested_col] == "Q"
end

return true
end

def safe_diag(suggested_row, suggested_col, row_mod, col_mod)
row,col = suggested_row+row_mod, suggested_col+col_mod
while true do

break if (row >= @n) || (col >= @n) || (row < 0) || (col < 0)

return false if @board[row][col] == "Q"

row += row_mod
col += col_mod
end

return true
end

def safe(suggested_row, suggested_col)

return false if !safe_row(suggested_row)
return false if !safe_col(suggested_col)

return false if !safe_diag(suggested_row, suggested_col, 1, 1)
return false if !safe_diag(suggested_row, suggested_col, 1, -1)
return false if !safe_diag(suggested_row, suggested_col, -1, 1)
return false if !safe_diag(suggested_row, suggested_col, -1, -1)

return true
end

def solve
solve_1(0)
end

def solve_1(row)
0.upto(@n-1) do |col|
if safe(row, col)
@board[row][col] = "Q"
if row == (@n-1)
print_board
else
solve_1(row+1)
end
@board[row][col] = "b"
end
end
end
end

board = Board.new(8).solve
```
6. Jos Koot said

http://en.wikipedia.org/wiki/Eight_queens_puzzle section ‘constructing a solution’ shows an algorithm that is linear in the number of columns of the board when implemented with a vector. It allows you to go to boardsizes up to N=200000000 (I can’t go higher because of memory)

```(define (queens N)
(if (and (exact-nonnegative-integer? N) (> N 3))
(let* ((R (remainder N 12))
(n-even (floor (/ N 2)))
(n-odd (- N n-even))
(V (make-vector N))
(set-V! (lambda (f r) (vector-set! V f r)))
(sema (make-semaphore 0)))
(let-syntax
((do-loop (syntax-rules ()
((for (x range ...) body ...)
(for ((x (in-range range ...))) body ...)))))
(λ ()
(case R
((3 9)
(do-loop (F 0 (sub1 n-even)) (set-V! F (+ (* 2 F) 3)))
(set-V! (sub1 n-even) 1))
(else (do-loop (F 0 n-even) (set-V! F (add1 (* 2 F))))))
(semaphore-post sema))) ; Signal completion.
(λ ()
(case R
((2)
(do-loop (F 2 (- n-odd 1)) (set-V! (+ F n-even) (+ (* 2 F) 2)))
(set-V! n-even 2)
(set-V! (sub1 N) 4))
((3 9)
(do-loop (F 0 (- n-odd 2)) (set-V! (+ F n-even) (+ (* 2 F) 4)))
(set-V! (- N 2) 0)
(set-V! (sub1 N) 2))
((8)
(do-loop (i 0 (sub1 n-odd) 2)
(set-V! (+ i n-even) (* 2 (add1 i)))
(set-V! (+ i n-even 1) (* 2 i))))
(else
(do-loop (F 0 n-odd) (set-V! (+ F n-even) (* 2 F)))))
(semaphore-post sema))) ; Signal completion.
(semaphore-wait sema) ; Wait for both loops to complete.
(semaphore-wait sema)
V))
(raise-type-error 'queens "exact integer greater than 3" N)))
```

8. programmingpraxis said

Here’s a different, somewhat simpler, solution in Scheme:

```(define (attack? q1 q2)   (or (= (car q1) (car q2))       (= (cadr q1) (cadr q2))       (= (abs (- (car q1) (car q2)))          (abs (- (cadr q1) (cadr q2))))))```

```(define (safe? q qs)   (cond ((null? qs) #t)         ((attack? q (car qs)) #f)         (else (safe? q (cdr qs)))))```

```(define (queens n)   (let queen ((n n) (x 1) (y 1) (qs '()) (qss '()))     (cond ((< n x) (cons (reverse qs) qss))           ((< n y) qss)           ((safe? (list x y) qs)             (queen n x (+ y 1) qs               (queen n (+ x 1) 1                 (cons (list x y) qs) qss)))           (else (queen n x (+ y 1) qs qss)))))```

9. Ying Yin said

Java implementation:

Source

10. simonliu2008 said

can any one tell me how to convert n-queens problem to exact cover problem?

11. programmingpraxis said

Knuth discusses this in his dancing links paper.

12. [...] problem with n queens on an n by n chessboard. After finding it again in older posts on both Programming Praxis and DataGenetics, I decided to go ahead and take a crack at it and I think the solution is pretty [...]