Share with others
8 Queen Problem
Aim: Implementation of 8 queen problem( Non recursive implementation) using
backtracking strategy
Objective: To study and understand the concept of backtracking.
Theory:
Backtracking
General method
• Useful technique for optimizing search under some constraints
• Express the desired solution as an ntuple (x1, . . . , xn) where each xi 2 Si, Si being a finite set
• The solution is based on finding one or more vectors that maximize, minimize, or satisfy a criterion function P(x1, . . . , xn)
• Sorting an array a[n]
– Find an ntuple where the element xi is the index of ith smallest element in a
– Criterion function is given by a[xi] _ a[xi+1] for 1 _ i < n
– Set Si is a finite set of integers in the range [1,n]
• Brute force approach
– Let the size of set Si be mi
– There are m = m1m2 · · ·mn ntuples that satisfy the criterion function P
– In brute force algorithm, you have to form all the m ntuples to determine the optimal solutions
• Backtrack approach
– Requires less than m trials to determine the solution
– Form a solution (partial vector) and check at every step if this has any chance of success
– If the solution at any point seems notpromising, ignore it
– If the partial vector (x1, x2, . . . , xi) does not yield an optimal solution, ignore mi+1 · · ·mn possible test vectors
even without looking at them
• All the solutions require a set of constraints divided into two categories: explicit and implicit constraints
Definition 1 Explicit constraints are rules that restrict each xi to take on values only from a given set.
– Explicit constraints depend on the particular instance I of problem being solved
– All tuples that satisfy the explicit constraints define a possible solution space for I
– Examples of explicit constraints
_ xi _ 0, or all nonnegative real numbers
_ xi = {0, 1}
_ li _ xi _ ui
Definition 2 Implicit constraints are rules that determine which of the tuples in the solution space of I satisfy the
criterion function.
– Implicit constraints describe the way in which the xis must relate to each other.
• 8queens problem
– Place eight queens on an 8 × 8 chessboard so that no queen attacks another queen
Backtracking

1

2

3

4

5

6

7

8

1




Q





2






Q



3








Q

4


Q







5







Q


6

Q








7



Q






8





Q




– Identify data structures to solve the problem
_ First pass: Define the chessboard to be an 8 × 8 array
_ Second pass: Since each queen is in a different row, define the chessboard solution to be an 8tuple (x1, . . . , x8),
where xi is the column for ith queen
– Identify explicit constraints
_ Explicit constraints using 8tuple formulation are Si = {1, 2, 3, 4, 5, 6, 7, 8}, 1 _ i _ 8
_ Solution space of 88 8tuples
– Identify implicit constraints
_ No two xi can be the same, or all the queens must be in different columns
· All solutions are permutations of the 8tuple (1, 2, 3, 4, 5, 6, 7, 8)
· Reduces the size of solution space from 88 to 8! tuples
_ No two queens can be on the same diagonal
– The solution above is expressed as an 8tuple as 4, 6, 8, 2, 7, 1, 3, 5
Share with others