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.
My Haskell solution (see http://bonsaicode.wordpress.com/2010/06/11/programming-praxis-n-queens/ for a version with comments):
[…] 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 […]
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.
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
Here’s a ruby version (commented at http://steamcode.blogspot.com/2010/06/n-queens-problem-in-ruby.html)
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)
Another usefull website about the N queens problem is http://sites.google.com/site/nqueensolver/
which has algorithms and executables for download
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)))))
Java implementation:
Source
can any one tell me how to convert n-queens problem to exact cover problem?
Knuth discusses this in his dancing links paper.
[…] 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 […]
Hi I am new to Ruby,I wrote a program in ruby which based on NQueen java program by Robert Sedgewick and Kevin Wayne http://introcs.cs.princeton.edu/java/23recursion/Queens.java.html,The problem is My program is not outputting the result,please help me here
my program source : http://repl.it/1jv