8 Queen Problem Chessboard

1. Let solve the 8-queen problem via a backtracking solution.

2. Let the chessboard squares is numbered as the indices of the two dimensional array a [1:n, 1:n], then every element on the same diagonal that runs from the upper left to lower right has the same row- column value.

3. Also every element on the same diagonal that goes from the upper right to lower left has the same row + column value.
4. Suppose two queen are placed at positions (i, j) and (k, l), then by the above they are on the same diagonal only if i - j=k-l or i + j=k + l.
5. The first equation implies j - l=i - k
6. The second equation implies j-l=k - i

7. Therefore two queens lie on the same diagonal if and only if j-l=i-k.

   Algorithm1: (Can a new queen be placed?)

• Algorithm Place(k, i)
• //Returns true if a queen can be placed in kth row and ith column otherwise it // returns //false. x [] is a global array whose first (k-1) value have been set.
• //Abs(r) returns the absolute value of r.
• {
  • For j:= 1 to k-1 do
  • If(x[j]=i) //Two in the same column
  • Or (Abs x[j]-i) = Abs(j-k))
  • //or in the same diagonal
  • Then return false;
  • Return true;
• }
• Above algorithm palce (k,i) returns a Boolean value that is true if the kth queen can be placed in column i.
• It tests both whether I is distinct from all previous values x [1]……..x[k-1] and whether there is no other queen on the same diagonal.
• It computing time O (k-1).
• The array x[] is a global
• The algorithm is invoked by N Queen (1, n).

Algorithm2: All solutions to the n-queen problems.

• Algorithm N Queens(k, n)
• //Using backtracking this procedure prints all possible placements of a queen on
• //an n*n chessboard so that they are non-attacking

• {

  • for i:= 1 to n do

  • {

    • If(Place(k,i)) then

      {

      x[k] := i;

      if(k=n) then write (x[1:n]);

      else N Queen(k+1,n);

      }

  • }
• }
• For an 8*8 chessboard there are (64/8) possible ways to place 8 pieces or approximate 4.4 billion 8-tuples to examine using brute force approach.
• However by allowing only placements of queens on distinct rows and columns, we require the examination of almost 8! Or only 40, 320, 8 tuples.