[Math] State space for 8-queen problem

artificial intelligencecombinatoricsprobability

While reading Artificial Intelligence a Modern Approach I came across the following formulation for the 8-queen problem:

  • Initial state: No queens on the board.
  • States: Arrangements of n queens (0 <= n <= 8), one per column in the leftmost n columns, with no queen attacking another are states.
  • Successor function: Add a queen to any square in the leftmost empty
    colum such that it is not attacked by any other queen.

I have been trying to find some pattern that would allow me to sort out the number of states for each n given the constraints above but I have not been succeeded for n > 2.

So, for:

  • n=1 => 8 states
  • n=2 => 42 states
  • …

Even though I could generate all the possible combinations for each n and then filter out all those that do not represent a valid state, I would rather not go that way because it would be really time and space consuming for n, say, greater or equal than 10.

To sum up, is there any sort of formula to find the number of states given n and at the same time taking into account the following constrains?

Best Answer

Here is a modest contribution while we wait for a professional answer to appear. You may be interested to know that even though the state space is easy to enumerate by backtracking, the numbers have not yet appeared in the OEIS!

The following Perl script implements the enumeration:

#! /usr/bin/perl -w
#

sub search {
    my ($sofar, $n, $sref) = @_;

    my $placed = scalar(@$sofar);

    $sref->{$placed}->{join('-', @$sofar)} = 1;
    return if $placed == $n;

    for(my $nxt = 0; $nxt < $n; $nxt++){
        my $ind;

        for($ind = 0; $ind < $placed; $ind++){
            last if $sofar->[$ind] == $nxt ||
                $ind + $sofar->[$ind] == $placed + $nxt ||
                $ind - $sofar->[$ind] == $placed - $nxt;
        }
        next if $ind != $placed;

        push @$sofar, $nxt;
        search($sofar, $n, $sref);
        pop @$sofar;
    }

    return;
}


MAIN: {
    my $mx = shift || 8;


    for(my $n=1; $n <= $mx; $n++){
        my $states = {};

        search([], $n, $states);

        printf "%02d: ", $n;

        for(my $placed = 1; $placed <= $n; $placed++){
            printf " %d",
            scalar(keys %{ $states->{$placed} });
        }

        print "\n";
    }
}

This yields the following data:

$ ./qs.pl 14
01:  1
02:  2 0
03:  3 2 0
04:  4 6 4 2
05:  5 12 14 12 10
06:  6 20 36 46 40 4
07:  7 30 76 140 164 94 40
08:  8 42 140 344 568 550 312 92
09:  9 56 234 732 1614 2292 2038 1066 352
10:  10 72 364 1400 3916 7552 9632 7828 4040 724
11:  11 90 536 2468 8492 21362 37248 44148 34774 15116 2680
12:  12 110 756 4080 16852 52856 120104 195270 222720 160964 68264 14200
13:  13 132 1030 6404 31100 117694 335010 707698 1086568 1151778 813448 350302 73712
14:  14 156 1364 9632 54068 241484 835056 2211868 4391988 6323032 6471872 4511922 1940500 365596

The OEIS has the number of solutions at OEIS A000170. I will try to see to it to enter the above triangular array into the OEIS giving the MSE post as one of the references.

Addendum. These data can now be found at OEIS A269133 where we hope additional useful references will appear (there are quite a number already which can be found in the linked to sequences).

Related Question