# June 29, 2017

## 8 Queens Puzzle

### Programming, 8 queens puzzle

Back in 1995 I wrote a program to brute force a solution to the 8 queens puzzle for the game The 7th Guest. It was the first time I recall using my programming skills to solve a real-world problem (although I had written a program to do my math homework prior to this). Prior to this all I had written were simply utilities and graphics demonstrations.

While driving on vacation I thought about this problem and wondered how I would solve it with the knowledge of programming I have today. Didn't take much thought before I decided I had to do an implementation.

The 8 queens puzzle is simple: positions 8 queens on a chess board such that no queen threatens any other. A queen in chess has the ability to move to any square in the same row, same column, or to any square along either diagonal. Thus any piece in this path is threatened.

A chess board contains 64 squares arranged in 8 rows and 8 columns. Since all I am trying to do is setup queens on the board I only need to know if a queen occupies a square or not. Thus I can represent the entire state of the board with a single 64-bit binary bitmap. The first bit is the first row, first column; second bit first row second column; 8th bit the second row, first columns; etc.

 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

In order to see what squares a queen threatens I need to construct a bitmap of the threatened squares based on the queen's location. The column is easy. Start with the first column of bits all set. Now shift left by the number of columns the queen is located.

 → → ♕

Rows are pretty much as simple. Start with the first row set and shift, but now shift by eight times the row location.

 ↓ ↓ ♕

Diagonals are more complected, but one starts with a full diagonal across the board and can shift based on the rows and columns to put it in the correct position.

 ↗ ♕ ↗ ↙ ♕ ↙

When you logically OR the results together you get a bitmap of what squares the queen threatens.

 ♕

What's useful here is that if we have a bitmap of the current positions of queens on the chess board and we make a threaten bitmap, logically ANDing the results will show you what pieces are threaten.

 ♕ ♕

Say we have the above board and want to place a queen in the third column on the second row.

 ♕ ♕ ♕

Here we see the threaten mask. If we AND the threaten mask with the playing field we get cells in red, showing we have a threatened queen by adding the one at the new position. As a binary operation, any non-zero result means there are threatened cells.

Treating the playing field as a bitmap makes threat testing very fast. Now for testing possible setups. For this I will use something I figured out back in 1995. We have 8 queens and 8 row/columns. Thus every row and column must have a queen. I start with all the queens on the first row, test this scenario, and if it fails, move the piece in the first column down a row and repeat. When the first column reaches the end, I move it back to the top and move the piece in the second column down one. This process repeats for all pieces in the row.

The question I had for myself was how to more efficiently implement this. There are only 8 possible rows which is a nice power of two (23). I could use 3-bits for each row, concatenated one after the other for each column. There are 8 pieces, each with 8 possibilities, or 88 = 16,777,216 possible locations which requires 24-bits. So I could simply have an incrementing counter that I break up into row/column. This requires 8 break-up and place operations per increment. However, this is what we want to do. Each time we increment, we start with a blank playing field. We then place each pieces at the specified row/column and then check for threats. If there is a threat, we can stop checking and move to the next increment. If all 8 pieces are placed without a threat, we have a solution. This is what I have implemented.

//=============================================================================
// Name: queens.c
// Uses: Print all possible combinations of placing 8 queens on chess board
//       without any queen threatening any other.
// Date: 2017-06-14
// Author: Andrew Que (https://www.DrQue.net/)
//
//                                Public Domain
//=============================================================================
#include <stdio.h>
#include <stdbool.h>
#include <inttypes.h>

// 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 };

// There 3-bits/row times 8 rows for a total of 2^24 possible board states.
enum { STATES = 1 << ( COLUMN_BITS * ROWS ) };

// Mask used to select bits for current column.
enum { COLUMN_BIT_MASK = ~-( 1 << COLUMN_BITS ) };

//-------------------------------------
// Base bit masks used for generating move mask.
//-------------------------------------

// Macro for setting the nth bit of a 64-bit constant.
#define BIT( n )  ( INT64_C( 1 ) << n )

// First entire first row set.
static uint64_t const ROW =
BIT( 0 ) | BIT( 1 ) | BIT( 2 ) | BIT( 3 ) | BIT( 4 ) | BIT( 5 ) | BIT( 6 ) | BIT( 7 );

// The entire first column set.
static uint64_t const COLUMN =
BIT( 0 ) | BIT( 8 ) | BIT( 16 ) | BIT( 24 ) | BIT( 32 ) | BIT( 40 ) | BIT( 48 ) | BIT( 56 );

// Top-left to bottom-right diagonal set.
static uint64_t const LEFT_DIAGONAL =
BIT( 0 ) | BIT( 9 ) | BIT( 18 ) | BIT( 27 ) | BIT( 36 ) | BIT( 45 ) | BIT( 54 ) | BIT( 63 );

// Top-right to bottom-left diagonal set.
static uint64_t const RIGHT_DIAGONAL =
BIT( 7 ) | BIT( 14 ) | BIT( 21 ) | BIT( 28 ) | BIT( 35 ) | BIT( 42 ) | BIT( 49 ) | BIT( 56 );

//-----------------------------------------------------------------------------
// Uses:
//   Set bit at row/column.
// Input:
//   row - Location's row (0-7).
//   column - Location's column (0-7).
// Returns:
//   Mask with set row/column.
//-----------------------------------------------------------------------------
static inline uint64_t set( unsigned row, unsigned column )
{
return UINT64_C( 1 ) << ( column + ( row * COLUMNS ) );
}

//-----------------------------------------------------------------------------
// Uses:
//   Generate a mask for all the moves a queen can make from given position.
// Input:
//   row - Location's row (0-7).
//   column - Location's column (0-7).
// Returns:
//   Mask with all move locations set.
//-----------------------------------------------------------------------------
static inline uint64_t queenMask( unsigned row, unsigned column )
{
// Diagonal mask from top-left to bottom-right.
uint64_t leftDiagonal = LEFT_DIAGONAL;
if ( row > column )
leftDiagonal <<= ( row - column ) * COLUMNS;
else
if ( row < column )
leftDiagonal >>= ( column - row ) * COLUMNS;

// Diagonal mask from top-right to bottom-left.
uint64_t rightDiagonal = RIGHT_DIAGONAL;
unsigned oppositeColumn = COLUMNS - column - 1;

if ( row > oppositeColumn )
rightDiagonal <<= ( row - oppositeColumn ) * COLUMNS;
else
if ( row < oppositeColumn )
rightDiagonal >>= ( oppositeColumn - row ) * COLUMNS;

// Start with a mask of the row and column moves covered.
uint64_t value = 0;
value |= ROW << ( COLUMNS * row );
value |= COLUMN << column;

// Add in diagonals moves.
value |= leftDiagonal;
value |= rightDiagonal;

return value;
}

//-----------------------------------------------------------------------------
// Uses:
//   Print an 8x8 mask representing the chess board.
// Input:
//   mask - Mask to be printed.
//-----------------------------------------------------------------------------
{
for ( unsigned row = 0; row < ROWS; row += 1 )
{
for ( unsigned column = 0; column < COLUMNS; column += 1 )
{
if ( BIT( 0 ) == ( mask & BIT( 0 ) ) )
putchar( 'x' );
else
putchar( '.' );

}

putchar( '\n' );
}

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;

// For every possible board state that contains 8 queens...
for ( uint_fast32_t state = 0; state < STATES; state += 1 )
{
// Initial field has no pieces on it.
uint64_t field = 0;

// Assume this is a valid arrangement.
bool isGood = true;

// 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 )
&& ( isGood ) )
{
// 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;

// Only check the field if there is at least one other piece on it.
if ( field > 0 )
{
// Generate mask for position covered by this move.
uint64_t mask = queenMask( row, column );

// If the move mask intersects with the current playing field, this
// setup is invalid.
if ( 0 != ( field & mask ) )
isGood = false;
}

// Add this move to the current field.
field |= set( row, column );

// Next row...
row += 1;
}

// If the loop finished and the setup is still good, this is one of the
// possible setups.
if ( isGood )
{
goodCount += 1;
}
}

// Display the total number of possible configurations.
printf( "Total: %u\n", goodCount );

return 0;
}

My old Pascal code took several seconds to find the first solution which takes around 1.3 million checks. On modern hardware this code will find all 96 solutions to the 8 queens puzzle in around 350 milliseconds, checking all 16.8 million possible combinations.

# June 30, 2017

## 8 Queens Puzzle Improvement

### Programming, 8 queens puzzle

In doing my write-up for the 8 queens puzzle article, I thought of a further improvement. I was creating a mask of threatened squares and checking the current layout of the chess board with it. However it occurred to me that we didn't need to check threats by row because the way the moves were being done only allowed a single piece per row. Thus there would never be common-row threat.

Then I started thinking about columns. If we simply marked a column as used, any new piece could simply check to see if that column was in use already and know the new piece was creating a threat. But what about diagonals?

For this I started with a labeling all the possible diagonals.

 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 8 2 2 3 4 5 6 7 8 9 3 3 4 5 6 7 8 9 10 4 4 5 6 7 8 9 10 11 5 5 6 7 8 9 10 11 12 6 6 7 8 9 10 11 12 13 7 7 8 9 10 11 12 13 14

The pattern for this diagonal is simple: the diagonal occupied by any piece is the row number plus the column number.

 0 1 2 3 4 5 6 7 0 7 8 9 10 11 12 13 14 1 6 7 8 9 10 11 12 13 2 5 6 7 8 9 10 11 12 3 4 5 6 7 8 9 10 11 4 3 4 5 6 7 8 9 10 5 2 3 4 5 6 7 8 9 6 1 2 3 4 5 6 7 8 7 0 1 2 3 4 5 6 7

The opposite diagonal is similar, but it is column plus 7 subtract row.

Both diagonals just require 14-bits, and the column check 8-bits. So I made a quick modification to my program.

//=============================================================================
// Name: queens.c
// Uses: Print all possible combinations of placing 8 queens on chess board
//       without any queen threatening any other.
// Date: 2017-06-15
// Author: Andrew Que (https://www.DrQue.net/)
//
//                                Public Domain
//=============================================================================
#include <stdio.h>
#include <stdbool.h>
#include <inttypes.h>

// 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 };

// There 3-bits/row times 8 rows for a total of 2^24 possible board states.
enum { STATES = 1 << ( COLUMN_BITS * ROWS ) };

// Mask used to select bits for current column.
enum { COLUMN_BIT_MASK = ~-( 1 << COLUMN_BITS ) };

//-----------------------------------------------------------------------------
// 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;

// For every possible board state that contains 8 queens...
for ( uint_fast32_t state = 0; state < STATES; state += 1 )
{
// Keep track of the columns and diagonals in use.  There can only ever
// be one piece per row so no need to check that.
uint_fast16_t columnUse = 0;
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;

// Check column and diagonals to see if this new piece creates a threat.
// If so, this setup is bad.
uint_fast16_t mask = ( 1 << column );
isBad |= ( columnUse & mask ) > 0;
isBad |= ( leftDiagonal & ( mask << row ) ) > 0;
isBad |= ( rightDiagonal & ( mask << ( 7 - row ) ) ) > 0;

// Mark the used column and diagonals.
leftDiagonal |= ( mask << row );
rightDiagonal |= ( mask << ( 7 - row ) );

// Next row...
row += 1;
}

// If the loop finished and the state is not bad, this is one of the
// possible layouts.
if ( ! isBad )
{
if ( false )
printState( state );
else
printf( "%08" PRIXFAST32 "\n", state );
goodCount += 1;
}
}

// Display the total number of possible configurations.
printf( "Total: %u\n", goodCount );

return 0;
}

The results produced by the program are identical. On the same computer as the first program I went from 350 ms to around 190 ms—a 54% speed improvement. Makes we wonder: what other improvements could be made?

# July 02, 2017

## 8 Queens Puzzle Improvement, part 2

### Programming, 8 queens puzzle

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 224 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 ] = { 00000000 };
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.

// 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.

// 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.

# July 05, 2017

## N-Queens Demonstration

### Math Demonstration, Programming, 8 queens puzzle

In implementing the 8 queens puzzle I decided to crate a Javascript interface that allows one to try and place queens on the chessboard of arbitrary size.

By clicking on a cell a queen is placed or removed. Highlighted cells show the threats created by placing a queen at that location. Yellow cells show that the highlighted area poses a threat. Red cells show the board is in conflict. A fully green board shows a solution.

One can generally find solutions to the smaller boards pretty quickly. The larger boards get very complected but also have more possible solutions. The solve button will use the method of permutations to try and find a random solution. For the larger boards it may not find a solution and will time out after 30 seconds. However, trying again will eventually produce a result and sometimes quite fast. It really depends on how the board was shuffled.  The total number of solutions to test for any board is n! where n is the number of rows/columns.

Rows/Columns Total Permutations
4 24
5 120
6 720
7 5,040
8 40,320
9 362,880
10 3,628,800
11 39,916,800
12 479,001,600
13 6,227,020,800
14 87,178,291,200
15 1,307,674,368,000
16 20,922,789,888,000
17 355,687,428,096,000
18 6,402,373,705,728,000
19 121,645,100,408,832,000
20 2,432,902,008,176,640,000

That last number is 2.4 quintillion. For comparison a computer counting at 4 billion counts/second (4 GHz) would take 19 years just to count that high.

Download a zip file of the project: nQueens_v1.0.zip. SHA256: a0de13bc06dd9a2cb8cde3b535939825946b07e8f8164b51fb6f2af89f0c7f11.