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 n-tuple (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 n-tuple 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 n-tuples that satisfy the criterion function P

– In brute force algorithm, you have to form all the m n-tuples 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 not-promising, 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.

• 8-queens problem

 

 

 

– Place eight queens on an 8 × 8 chessboard so that no queen attacks another queen

Backtracking

– 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 8-tuple (x1, . . . , x8),

where xi is the column for ith queen

– Identify explicit constraints

_ Explicit constraints using 8-tuple formulation are Si = {1, 2, 3, 4, 5, 6, 7, 8}, 1 _ i _ 8

_ Solution space of 88 8-tuples

– 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 8-tuple (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 8-tuple as 4, 6, 8, 2, 7, 1, 3, 5