Scribd
Upload
51 views3 pages

N Queens: Backtracking: General Form

Backtracking is an algorithmic technique for solving problems recursively by trying all possible candidates for the solution. It allows pruning the search space by not exploring branches that cannot possibly lead to a valid solution. The N Queens problem, which involves placing N queens on an N×N chessboard so that no two queens attack each other, can be solved using backtracking. It recursively tries placing queens on each row while checking that constraints are not violated. If a partial placement leads to a violation, that branch is pruned from the search tree. This allows finding solutions more efficiently than exploring all possible placements exhaustively.

Uploaded by

farha19
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
51 views3 pages

N Queens: Backtracking: General Form

Backtracking is an algorithmic technique for solving problems recursively by trying all possible candidates for the solution. It allows pruning the search space by not exploring branches that cannot possibly lead to a valid solution. The N Queens problem, which involves placing N queens on an N×N chessboard so that no two queens attack each other, can be solved using backtracking. It recursively tries placing queens on each row while checking that constraints are not violated. If a partial placement leads to a violation, that branch is pruned from the search tree. This allows finding solutions more efficiently than exploring all possible placements exhaustively.

Uploaded by

farha19
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Backtracking, despite its exponential-time behavior, continues to arise in

problems for which no better solution method is known. A lot of effort goes into
finding ways to speed up its average performance.

Backtracking is to constraint satisfaction as branch and bound is to optimization.

Backtracking: General Form


type checknode(node v)
if (promising(v))
if (solution(v))
write solution
else
for each child node u of v
checknode(u)
There are 3 "pseudo-functions" in here:

 First, there is solution(v): checking to see if all constraints are satisfied.


 There is promising(v): seeing if the node does not break all constraints
 checknode(v): called only if constraint is satisfied and node is not solution.

N Queens
 When N = 1, 1 queen can be placed on a 1x1 board so that it doesn't threaten
another.
 When N = 2, 2 queens cannot be placed on a 2x2 board because all
configurations would put both in danger.
 When N = 3, this is more complicated. You still can't do it though.
 When N = 4, this is possible. You put each queen on an edge, one space
away from each corner.

If we try recursive solution for this. First, note that there has to be exactly one queen
on each row.

When you insert a queen on the first row, you can put it anywhere. Easy. Now, when
you put the next queen in the second row, let's say you put it in the first (or second)
column. Both of these configurations would not work, since the other queen could
attack it. Now, you don't have to search any further configurations with those
two queens in those positions. That's the beauty of backtracking.

On eight queens, the search space has 16 million different possibilities. There are 92
solutions to the eight queens problem. Using backtracking, you only have to look at
around 15,000 branches.

In summary, backtracking lets us look at every possible state in the tree, but in a
smart way: it lets us cut off anything we don't want to consider.
Partitioning the array by choosing pivot as the middle
element
The key to the algorithm is the partition procedure, which arranges the sub
array A[p . . r] in place.

PARTITION(A,p,r)
1 x A[p]
2 i p-1
3 j r+1
4 while TRUE
5 do repeat j j - 1
6 until A[j] x
7 repeat i i + 1
8 until A[i] x
9 if i < j
10 then exchange A[i] A[j]
11 else return j

Above algorithm shows how PARTITION works. It first selects an element x = A[p]
from A[p . . r] as a "pivot" element around which to partition A[p . . r]. It then
grows two regions A[p . . i] and A[j . . r] from the top and bottom of A[p . . r],
respectively, such that every element in A[p . . i] is less than or equal to x and every
element in A[j . . r] is greater than or equal to x. Initially, i = p - 1 and j = r + 1, so
the two regions are empty.

Within the body of the while loop, the index j is decremented and the index i is
incremented, in lines 5-8, until A[i] x A[j]. Assuming that these inequalities are
strict, A[i] is too large to belong to the bottom region and A[j] is too small to
belong to the top region. Thus, by exchanging A[i] and A[j] as is done in line 10,
we can extend the two regions. The body of the while loop repeats until i j, at
which point the entire array A[p . . r] has been partitioned into two subarrays A[p . .
q] and A[q + 1 . . r], where p q < r, such that no element of A[p . . q] is larger than
any element of A[q + 1. . r]. The value q = j is returned at the end of the procedure.

Conceptually, the partitioning procedure performs a simple function: it puts


elements smaller than x into the bottom region of the array and elements larger
than x into the top region. There are technicalities that make the pseudocode
of PARTITION a little tricky, however. For example, the indices i and j never index
the subarray A[p . . r] out of bounds, but this isn't entirely apparent from the code.
As another example, it is important that A[p] be used as the pivot element x. If A[r]
is used instead and it happens that A[r] is also the largest element in the
subarray A[p . . r], then PARTITION returns to QUICKSORT the value q = r,
and QUICKSORT loops forever. Problem 8-1 asks you to prove PARTITION correct.
Figure above shows The operation of PARTITION on a sample array. Lightly
shaded array elements have been placed into the correct partitions, and
heavily shaded elements are not yet in their partitions. (a) The input
array, with the initial values of i and j just off the left and right ends of the
array. We partition around x = A[p] = 5. (b) The positions of i and j at line 9
of the first iteration of the while loop. (c) The result of exchanging the
elements pointed to by i and j in line 10. (d) The positions of i and j at line 9
of the second iteration of the while loop. (e) The positions of i and j at line
9 of the third and last iteration of the while loop. The procedure
terminates because i j, and the value q = j is returned. Array elements up
to and including A[j] are less than or equal to x = 5, and array elements
after A[j] are greater than or equal to x = 5.

The running time of PARTITION on an array A[p . . r] is (n), where n = r - p + 1

You might also like