0
18kviews
Explain 8 Queen Problems.
1 Answer
1
757views

8 Queen Problem Chessboard

          Q    
      Q        
            Q  
Q              
    Q          
        Q      
  Q            
              Q
  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.
Please log in to add an answer.