Solving 8-Queens Problem by Generating Permutations: A Swapping Algorithm

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

A Swapping Algorithm

An earlier article titled Generating Permutations with Recursion [1] discusses a permutation generation algorithm by C. T. Fike which can be modiﬁed to solve the 8-Queens Problem (refer method ﬁke() in its section “Fike’s Algorithm”). Instead of searching, it systematically locates the next element to place at index s.

The modiﬁed method is shown below with all added lines marked using /* 8Q */. Unlike permute(), array a needs to be initialized in this case. For other initializations, the earlier shown init() method should be used.

int a[] = {0, 1, 2, 3, 4, 5, 6, 7};

#define SWAP(i, j) {int t; t = a[i]; a[i] = a[j]; a[j] = t;}

void fike_8queens(int s)
{
  int i;

  if(s == N-1)
  {
    if(prefix_extensible(s, a[s]))                    /* 8Q */
      print();

    return;
  }

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

    if(i > 0)
      SWAP(s, s+i);

    prefix_extended(s);                               /* 8Q */

    fike_8queens(s+1);

    prefix_reduced(s);                                /* 8Q */

    if(i > 0)
      SWAP(s, s+i);
  }
}

Notice how, adding a few steps to the two permutation generation methods (permute() and ﬁke()), gave us methods to solve an initially dissimilar 8-Queens Problem.

For both these methods, we could skip the recursive call (for argument (s + 1)) whenever required and could still uphold the correctness of the permutation generation logic with ease. We may be able to use other permutation generation algorithms too (e.g. from article [1]) for the 8-Queens Problem, but introduction of such skipping may demand other changes to ensure their correctness.

References

[1] Nitin Verma. Generating Permutations with Recursion. https://
mathsanew.com/articles/permutations_with_recursion.pdf.