# 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.
//-----------------------------------------------------------------------------
static void printMask( uint64_t mask )
{
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( '.' );

mask >>= 1;
}

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 )
{
printMask( field );
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 28, 2017

Pictured is a backhoe and bulldozers working on clearing snow around Logan Pass at Glacier National Park.  I was maybe a mile from where they were working before I turned around on my ride.  The snow they are working on is several feet deep.  They cannot use their giant snowblowers because this snow comes from avalanches which in addition to snow contains large rocks ripped off the mountain side.  So they have to use a backhoe and shovel the snow over the edge.  This picture is June 2nd and the snow crews have been working since April.  Today the Going-to-the-Sun Road through Glacier National is officially open.  This is a little latter than usual because of the higher than normal snowfall during the winter.
The snow crew at Glacier flights this battle every year in order to allow a 50 mile stretch of road to provide access though these beautiful mountains, and I am very glad they do.

# June 27, 2017

Glacier National does this.  In the morning the mountains were hiding in the clouds, and by afternoon it was bright and sunny.  It's like two different worlds, and I have to admit I like them both.  I have been to more than 10 national parks including several of the most well known such as Yellowstone, Yosemite, and the Grand Canyon.  Of all the parks, Glacier National has to be my favorite.

# June 26, 2017

Horses on the south side of Glacier National Park.  They are on both sides of the fence which has been flattened in areas.  I'm not sure what happened to the fence or if the rancher knows his horses can wondering freely to the road, but it did make for some lovely pictures.

# June 25, 2017

My first night in Canada I camped in Banff.  At 11:00 pm it was still twilight and I took a short ride to take some evening photography.  I did a few shots with the moon, stars, trees and mountains.  In this shot I used the headlight on my bike to illuminate some trees.

# June 24, 2017

This is the town of Banff in Alberta, Canada as seen from atop Sulphur Mountain.  What I find interesting is that in the middle of this picture is Tunnel Mountain.  It has a prominence of 1,001 feet, but it looks like a hill when seen next to the surrounding mountains.  The bluff around Devil's Lake in Baraboo, Wisconsin has a prominence of around 500 feet.

# June 23, 2017

Zach and Pokie trying to look disingenuous at breakfast this morning.

# June 22, 2017

Dinner this evening with Liz and Devon.

# June 21, 2017

While visiting Morine Lake in Alberta I arrived as to kind of accident where helicopter rescue had to assist.  I don't know any of the details of what happened, but a tourist location with lots of hikers in mountains probably meant a fall.  Rescue helicopter pilots I've always found impressive and it was interesting to watch one at work.

# June 20, 2017

When at the campsites in Canada I was unable to find any suitable small branches to make a marshmallow stick.  So, I used an unsuitable one.  The branch I found was quite straight but about 3 inches in diameter.  So I used my hatchet to make a pointy tip and then a knife to make a sharp point.  Worked very well.  The straightness of the branch allowed me to turn the marshmallow and get an even warming on all sides.  I left the ridiculous thing so maybe the next camper at our site could enjoy a giant marshmallow stick that did a good job.