Solving 8-Queens Problem by Generating Permutations: An Algorithm

[This page is auto-generated; please prefer to read the article’s PDF Form.]

An Algorithm

A trivial method is to generate all the 8! permutations of ℤ8 (using some permutation generation algorithm) and for each permutation check whether it satisﬁes the constraint C.

But a simple observation can help us optimize. Any permutation of m integers from ℤ8 (m < 8) is actually a preﬁx of some complete permutations of the 8 integers. Let us refer any such permutation as “permutation-preﬁx”. If a permutation-preﬁx does not satisfy constraint C for its m elements, then any permutation of the 8 integers starting with this permutation-preﬁx will not satisfy the constraint too; there are (8 −m)! such permutations. It means, we will not need to check these (8 −m)! permutations individually, and can reject them as a whole.

To utilize this observation, we will generate permutations in such a way that all permutations starting with a common permutation-preﬁx (of any length) get generated together as a separable subtask. So, if a permutation-preﬁx is found to violate the constraint, we can easily skip the generation (and checking) of all permutations sharing this preﬁx.

One such way of generating permutations has been shown below (for integers in ℤ8), implemented in C. It need not be an eﬃcient permutation generation algorithm, but is simple to understand. permute(s) is supposed to generate all permutations of the integers not already placed till index (s − 1), over indices s to N − 1. print() prints the complete permutation from array a.

#define N 8

/* below array declarations assume N = 8 */

int a[8];

/* boolean array to track the integers (0 to 7) which have
   already been placed in the permutation being constructed */
char placed[] = {0, 0, 0, 0, 0, 0, 0, 0};

void permute(int s)
{
  int i;

  if(s == N)
  {
    print();
    return;
  }

  for(i = 0; i < N; i++)
  {
    if(!placed[i])
    {
      a[s] = i;
      placed[i] = 1;

      permute(s+1);

      placed[i] = 0;
    }
  }
}

void print()
{
  int i;

  for(i = 0; i < N; i++)
    printf("%d ", a[i]);

  printf("\n");
}

We will now modify this permutation generation method to solve the 8-Queens Problem. As mentioned earlier, if a permutation-preﬁx violates the constraint, we will skip generating (and checking) all permutations sharing this preﬁx. This skipping becomes easy here because all such permutations would get generated under a single recursive call permute(s + 1).

To record the (r − a_r) and (r + a_r) values already taken by the current permutation-preﬁx, we will use two boolean arrays. The modiﬁed method is shown below with all added lines marked using /* 8Q */. Method init() should be called ﬁrst for doing initializations.

/* boolean arrays to track "r plus a[r]" (rpar) which ranges from
   0 to 14, and "r minus a[r]" (rmar) which ranges from -7 to 7.
   The values of (r+a[r]) and (r-a[r]+7) will be used to index
   into these arrays. */
char rpar[15], rmar[15];

/* can the permutation-prefix be extended by placing "e" at
   index "r", without violating constraint C ? */
#define prefix_extensible(r, e) (!rpar[r+e] && !rmar[r-e+7])

/* the permutation-prefix was extended by including index "r" */
#define prefix_extended(r) {rpar[r+a[r]] = 1; rmar[r-a[r]+7] = 1;}

/* the permutation-prefix was reduced by excluding index "r" */
#define prefix_reduced(r) {rpar[r+a[r]] = 0; rmar[r-a[r]+7] = 0;}

void init()
{
  memset(rpar, 0, 15*sizeof(char));
  memset(rmar, 0, 15*sizeof(char));
}

void permute_8queens(int s)
{
  int i;

  if(s == N)
  {
    print();
    return;
  }

  for(i = 0; i < N; i++)
  {
    if(!placed[i])
    {
      if(!prefix_extensible(s, i))                    /* 8Q */
        continue;                                     /* 8Q */

      a[s] = i;
      placed[i] = 1;
      prefix_extended(s);                             /* 8Q */

      permute_8queens(s+1);

      placed[i] = 0;
      prefix_reduced(s);                              /* 8Q */
    }
  }
}

For placing element at index s, this permutation generation algorithm searches for an element which is not already placed till index (s− 1). We will now see a more eﬃcient algorithm to generate permutations.