github: https://github.com/DoctorLai/Algorithms/tree/master/Queen
n Queen problem can be dated back in 1848. Later, it was popular used in computer algorithm books that teach data structure and algorithms. The problem is to find the number of ways to put n queens in n x n size of chess board so that each queens do not attach each other (vertically, horizontally and diagonally).
For example, the following is a solution of 8 queen problem.
The algorithm to search for solution is to check one by one (row by row or column by column) and place each queen individually. The counter (answer) will be incremented by one if n queens are placed sucessfully.
If queens can be placed diagonally, the total solutions would be 
The following is recursive back tracing that tries to iterate each valid solution.
#!/usr/bin/env python
# https://helloacm.com
from time import *
# size of queen
n = 10
# recursive back tracing
ans = 0
sol = [0] * n
def chk(sol, depth):
if depth == 0:
return True
for i in xrange(0, depth):
if sol[i] == sol[depth]:
return False
if abs(i - depth) == abs(sol[i] - sol[depth]):
return False
return True;
def work(depth, row):
global sol, ans, n
if depth == n:
ans += 1
return
for i in xrange(0, n):
sol[depth] = i
if chk(sol, depth):
work(depth + 1, 0)
start = time()
work(0, 0)
print time() - start
print ans
The timing on 8GB, Intel Core7, Win7 is 0.628999948502 seconds for 10 queens.
The other quick implementation is based on bit-logic operations. It is extremely fast. The following is the approach.
#!/usr/bin/env python
# https://helloacm.com
from time import *
# size of queen
n = 10
# bit hack version
ans = 0
LIM = (1 << n) - 1
def queen(row, ld, rd):
# row: which queen
# ld: left diag
# rd: right diag
global ans, LIM
if row == LIM:
ans += 1
return
pos = LIM & (~(row | ld | rd)) # valid positions
while pos != 0:
p = pos & (-pos) # try rightmost one
pos -= p;
queen(row + p, (ld + p) << 1, (rd + p) >> 1) # recursive next queen
start = time()
queen(0, 0, 0)
print time() - start
print ans
On the same problem-scale, same machine, it finds the solution within 0.024 seconds, which is a lot faster than the above approach.
The queen function takes three parameters, row, ld, rd representing the forbidden places of current row, left diagonal and right diagonal respectively.
The row | ld | rd combines all invalid positions. ~ is the boolean not operation which gives the valid position. p & -pos equals to the right-most one. i.e. -pos = ~pos + 1
Then on next recursive call, we try the next queen by updating the forbidden places. When the row equals to all ones, we have a solution and increase the counter by one. Simple, powerful and effective!
Other classic implementations of backtracking algorithms to solve the N queen problem: Using Recursive Backtracking Algorithm to Solve Classic N Queen Problem
See other implementations of N-Queen Problems:
- Algorithm to Valid N Queens
- Teaching Kids Programming – Backtracking Algorithm to Solve N-Queen Problem
- Using Recursive Backtracking Algorithm to Solve Classic N Queen Problem
- Find the Queens That Can Attack the King
- N Queen Problem in Back Tracing, Bit-logics
- Coding Exercise – N Queen Problem – C++ – Bit Logics – Shortest and Fastest Solution – Online Judge
- N Queen Problem in Back Tracing, Bit-logics
–EOF (The Ultimate Computing & Technology Blog) —
Last Post: Simple Calculation without Integration
Next Post: Interview Question: 2^n - 1 divide by 7