N-Queens
June 11, 2010
We present today a classic exercise that has been on my to-do list since the start of Programming Praxis.
The n-queens problem is to find all possible ways to place n queens on an n × n chess board in such a way that no two queens share a row, column, or diagonal. The diagram at right shows one way that can be done on a standard 8 × 8 chess board.
Your task is to write a program to find all such placements. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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