Shortly after finishing my last article about improving the 8 queens puzzle solver I thought up another improvement. This one took longer to figure out an implementation.

I had setup a brute-force method of solving where I tested every possible board layout with one queen in each row. However most of these are known to not be solutions. Every solution must have a single queen in each row, and in each column. Otherwise we know there is a row/column threat.

So how to we iterate over fields with one queen in each row and column? To start with I considered the simplest possible board.

Here we just have each queen occupy it's row/column index. We can generate each of the remaining possible fields by swapping rows. Then with every possible combination there will still be a single queen for each row and column. The number of possible combinations is a simple permutations problem. Since we have 8 rows we could swap around, the number of permutations is 8! or 40,320. That is a lot less than the 2^{24} or 16.8 million possibilities we test in my previous methods.

The problem I had was how to iterate through the permutations. After thinking about the problem for awhile I found a parallel-permutation. The various combinations of rows was the same as if we had 8 letters to rearrange. I was pretty sure someone had come up with an efficient way to iterate through such combinations so I just had to find it. Doing a little searching I came across Heap's Algorithm. With some tweaks to the pseudocode I found in the example I had a loop that would produce each variation of the playing field that I could test. Once that work I just plugged in the test code. It produced 92 results but I had to make sure it came up with the same 92 results.

I would typically just check to see that the output from the new program matched the old, but the order in which functional boards are found is different. Since I store the board state as a 64-bit bitmap I could simply print the 64-bit value, then sort, and compare. Sure enough my new version comes up with identical results.

//=============================================================================

// Name: queens.c

// Uses: Print all possible combinations of placing 8 queens on chess board

// without any queen threatening any other.

// Date: 2017-06-19

// Author: Andrew Que (https://www.DrQue.net/)

//

// Public Domain

//=============================================================================

#include <stdio.h>

#include <stdbool.h>

#include <inttypes.h>

// True to print the complete layout, false for just a hex representation.

// True for normal operation, false sometimes useful for debug.

static bool const FULL_PRINT = false;

// Rows/columns on a chess board.

enum { ROWS = 8 };

enum { COLUMNS = 8 };

// The board state uses 3-bits/row. This is because there are 8 columns and 2^3 = 8.

enum { COLUMN_BITS = 3 };

// Mask used to select bits for current column.

enum { COLUMN_BIT_MASK = ~-( 1 << COLUMN_BITS ) };

// Number of board permutations needing to be checked. This is the number of

// possible combinations to arrange the board such that there is a queen in

// each row and column.

enum { PERMUTATIONS = 8*7*6*5*4*3*2 }; // 8!

//-----------------------------------------------------------------------------

// Uses:

// Print an 8x8 grid representing the queen placements for the given state.

// Input:

// state - State of chess board.

//-----------------------------------------------------------------------------

static void printState( uint_fast32_t state )

{

for ( unsigned row = 0; row < ROWS; row += 1 )

{

// Column selected in this row.

unsigned selectedColumn = ( state & COLUMN_BIT_MASK );

state >>= COLUMN_BITS;

char rowText[] = "........";

rowText[ selectedColumn ] = 'x';

puts( rowText );

}

putchar( '\n' );

}

//-----------------------------------------------------------------------------

// Uses:

// Display all the possible combinations of placing 8 queens on a chess board.

// Output:

// Always returns 0.

//-----------------------------------------------------------------------------

int main()

{

// Number of functional board layouts.

unsigned goodCount = 0;

// Initial state just has a queen in each row and each column.

uint_fast32_t state =

UINT32_C( 0 ) << ( 0 * COLUMN_BITS )

| UINT32_C( 1 ) << ( 1 * COLUMN_BITS )

| UINT32_C( 2 ) << ( 2 * COLUMN_BITS )

| UINT32_C( 3 ) << ( 3 * COLUMN_BITS )

| UINT32_C( 4 ) << ( 4 * COLUMN_BITS )

| UINT32_C( 5 ) << ( 5 * COLUMN_BITS )

| UINT32_C( 6 ) << ( 6 * COLUMN_BITS )

| UINT32_C( 7 ) << ( 7 * COLUMN_BITS );

uint_fast8_t permutations[ ROWS ] = { 0, 0, 0, 0, 0, 0, 0, 0 };

unsigned permutationIndex = 0;

// For every possible board state that contains 8 queens...

for ( uint_fast32_t permutation = 0; permutation < PERMUTATIONS; permutation += 1 )

{

// Keep track of the diagonals in use. There can only ever

// be one piece per row or column so no need to check that.

uint_fast16_t leftDiagonal = 0;

uint_fast16_t rightDiagonal = 0;

// True if the current state has threats. Assumes none at start.

bool isBad = false;

// Current row (0-7).

unsigned row = 0;

// Sub-state is a copy of state, but shifted as column bits are used.

uint_fast32_t subState = state;

// Loop through all rows, adding queens until all are placed or any of the

// queens threaten another.

while ( ( row < ROWS )

&& ( ! isBad ) )

{

// Each row must have a queen, so we just need to calculate the

// column the queen is located from the game state.

unsigned column = subState & COLUMN_BIT_MASK;

subState >>= COLUMN_BITS;

// Mask for the bits in the associated diagonal mask.

uint_fast16_t leftDiagonalMask = ( 1 << ( column + row ) );

uint_fast16_t rightDiagonalMask = ( 1 << ( column + ROWS - 1 - row ) );

// Check diagonals to see if this new piece creates a threat.

// If so, this setup is bad.

isBad |= ( leftDiagonal & leftDiagonalMask ) > 0;

isBad |= ( rightDiagonal & rightDiagonalMask ) > 0;

// Mark the appropriate diagonals as used.

leftDiagonal |= leftDiagonalMask;

rightDiagonal |= rightDiagonalMask;

// Next row...

row += 1;

}

// If the loop finished and the state is not bad, this is one of the

// possible layouts.

if ( ! isBad )

{

// Show this layout.

if ( FULL_PRINT )

printState( state );

else

printf( "%06" PRIXFAST32 "\n", state );

goodCount += 1;

}

//

// Use Heap's algorithm to iterate through all permutations.

//

// Setup swap locations.

unsigned indexA = permutationIndex * COLUMN_BITS;

unsigned indexB = 0;

if ( 1 == ( permutationIndex & 1 ) )

indexB = permutations[ permutationIndex ] * COLUMN_BITS;

// Masks for swap.

uint_fast32_t leftDiagonalMask = COLUMN_BIT_MASK << indexA;

uint_fast32_t rightDiagonalMask = COLUMN_BIT_MASK << indexB;

// Swap the two bit maps.

state = 0

| ( state & rightDiagonalMask ) << ( indexA - indexB )

| ( state & leftDiagonalMask ) >> ( indexA - indexB )

| ( state & ~( leftDiagonalMask | rightDiagonalMask ) );

// Advance permutation index.

permutations[ permutationIndex ] += 1;

permutationIndex = 0;

// Add plus carry for all permutations indices.

while ( permutations[ permutationIndex ] >= permutationIndex )

{

permutations[ permutationIndex ] = 0;

permutationIndex += 1;

}

} // for loop.

// Display the total number of possible configurations.

printf( "Total: %u\n", goodCount );

return 0;

}

The code is very similar to the previous implementation with the new code being in how the state is generated from the permutations. The check code is smaller because we don't need to check for a column threat—each columns is guaranteed a single queen.

The speed of the new version is hardly comparable. Tests show it takes around 24 ms, but that number is low enough to have interference from the operating system scheduler. The improvement is around 9 times faster than the initial implementation, and 8 times the first improvement. Almost all of this speed is due to the fact there are more than 400 times as many checks to preform with the original implementations compared with the new.

Further improvements are possible. I could come up with more efficient ways to iterate, or even see about finding some tricks to iterate over scenarios with known diagonal threats. However I am pretty satisfied with this solution. I also learned a new algorithm as a result and who knows when need of such a thing will arise.