Transcript Backtrack: 8

Backtrack: 8-queen
Edit from old slide since 2000
P. Chongstitvatana 26 Nov 2010
Backtracking
Eight queens problem
1 try all possible C64 8 = 4,426,165,368
2 never put more than one queen on a
given row,
vector representation : each row specify
which column (3,1,6,2,8,6,4,7)
1 2 3 4 5 6 7 8
X
X
X
X
X
X
X
X
(3,1,6,2,8,6,4,7)
Queen1
for i1 = 1 to 8 do
for i2 = 1 to 8 do
....
for i3 = 1 to 8 do
sol = [i1, i2, . . . i8 ]
if solution ( sol ) then write sol stop
write “there is no solution”
Num. Of positions = 8 8 = 16,777,216
(first soln after 1,299,852 )
3 Never put queen on the same row
(different numbers on soln vector)
Queen2
sol = initial-permutation
while sol != final-permutation and not solution(sol)
do
sol = next-permutation
if solution(sol) then write sol
else write “there is no solution”
Permutation
T[1 . . n] is a global array initialize to [1,2,. . n]
initial call perm(1)
Perm(i)
if i = n then use T
else for j = i to n do exchange T[i] and T[j]
perm(i+1)
exchange T[i] and T[j]
Number of positions 8! = 40,320 (first soln after 2830)
8-queen as tree search
a vector V[1. .k] of integers between 1 and 8 is
k-promising, if none of the k queens threatens
any of the others.
A vector V is k-promising if, for every pair of
integers i and j between 1 and k with i != j, we
have V[i] - V[j] is-not-in {i-j, 0, j-i}.
Solutions to the 8-queen correspond to vectors
that are 8-promising.
Let N be the set of k-promising vectors, k: 0 .. 8.
Let G = (N,A) be the directed graph such that
(U,V) is-in A iff there exists an integer k, k:0..8 ,
such that
•U is k-promising
k=0
•V is (k+1)-promising, and
•U[i] = V[i] for every i in [1..k]
Number of node < 8!
(node 2057, first soln after 114 )
...
k=8
General Template for backtracking
Backtrack ( v[1..k] )
// v is k-promising vector
if solution ( v ) then write v
else for each (k+1)-promising vector w
such that w[1..k] = v[1..k]
do backtrack( w[1.. k+1] )