Subscribe to Nathan Mullenax's Blog

## 8 Queens Puzzle in C++

This is the first backtracking algorithm I've implemented. It finds all unique (up to rotation, transposition, mirroring, etc) solutions to the following problem:

Place 8 queens on a standard chess board such that no queen is threatening any other queen. It's gotten a lot more messy since I profiled and optimized it, but the basic approach is a breadth-first search over all possible boards. At every placement, a board state is tested to see if is a valid partial solution; if not, it is eliminated from the search tree.

```#include <iostream>
#include <vector>
#include <set>
#include <stdlib.h>

// solve 8 queens problem w/ backtracking
typedef struct
{
unsigned char rows[8];
} partial_p;

typedef union
{
partial_p p;
unsigned long long cmp;
} partial;

static inline bool
getbit( partial const & p, int bit )
{
return ((p.cmp >> bit)&1)==1;
}

static inline bool
getbit( partial const & p, int x, int y )
{
return getbit(p,x+(y<<3));
}

void
print_solution( partial const & p )
{
std::cout << "\n";
for(int y=0; y<8; ++y)
{
for(int x=0; x<8; ++x)
{
std::cout << (getbit(p,x,y)?"1":"-");
}
std::cout << "\n";
}
}

inline bool
operator< ( partial const & a, partial const & b )
{
return a.cmp < b.cmp;
}

std::set<partial> solutions;

static inline void
setbit( partial &p, int bit )
{
unsigned long long mask = 1;
}

static inline partial
flipv( partial const & p )
{
partial q;
for(int i=0; i<8; ++i)
{
q.p.rows[i] = p.p.rows[7-i];
}
return q;
}

static inline partial
fliph( partial const & p )
{
partial q;
q.cmp = 0;
for(int i=0; i<8; ++i)
{
// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
q.p.rows[i] = (p.p.rows[i] * 0x0202020202ULL & 0x010884422010ULL) % 1023;
}
return q;
}

static inline partial
transpose( partial const & p )
{
partial q;
q.cmp = 0;
for(int y=0; y<8; ++y)
{
for(int x=0; x<8; ++x)
{
if(getbit(p,x+(y<<3)) )
setbit(q,(x<<3)+y);
}
}
return q;
}

static inline bool
valid_cols_n_rows( partial const & p )
{
bool valid(true);
unsigned char taken(0);
unsigned char c;
for(int i=0; valid && i<8; ++i)
{
c = p.p.rows[i];
valid = valid && ((taken & c)==0);
valid = valid && ((c & (c-1))==0);  // 0 or 2^k
taken |= p.p.rows[i];
}
return valid;
}

static inline bool
validdiags( partial const & p )
{
static int sums[30];

for(int i=0; i<30; ++i)
{
sums[i]=0;
}

for(int y=0; y<8; ++y)
{
for(int x=0; x<8; ++x)
{
// this pixel falls in two different diagonals
if( getbit(p,x,y) )
{
// negative diagonals
sums[x+y]++;     // x+y goes 0..14
sums[x-y+22]++;
if(sums[x+y]>1||sums[x-y+22]>1)
return false;
}
}
}

return true;
}

bool
valid( partial const & p )
{
//return validrows(p) && validcols(p) && validdiags(p);
return valid_cols_n_rows(p) && validdiags(p);
}

void
compute_partials( std::vector<partial> & ps, partial const & p )
{
for(int i=0; i<64; ++i)
{
if( !getbit(p,i) )
{
partial pp = p;
setbit(pp,i);
if( valid(pp) )
{
ps.push_back(pp);
}
}
}
}

bool unique( partial const & p )
{
partial q;
if( solutions.count(p)>0 )
return false;
q = flipv(p);
if( solutions.count(q)>0 )
return false;
q = fliph(q);
if( solutions.count(q)>0 )
return false;
q = flipv(q);
if( solutions.count(q)>0 )
return false;
q = transpose(q);
if( solutions.count(q)>0 )
return false;
q = flipv(q);
if( solutions.count(q)>0 )
return false;
q = fliph(q);
if( solutions.count(q)>0 )
return false;
q = flipv(q);
if( solutions.count(q)>0 )
return false;
return true;
}

int
main()
{
partial p;
p.cmp = 0;
solutions.insert(p);

std::cout << "--------------------------------------------------------------\n";
std::cout << "This program solves the 8-queens problem on an 8x8 grid.      \n";
std::cout << "The point of this problem is to find positions for 8 queens.  \n";
std::cout << "on a chessboard such that none of them can attack one another.\n";
std::cout << "--------------------------------------------------------------\n\n";

std::cout << "Press enter to begin...\n";
std::cin.ignore();

for(int i=0; i<8; ++i)
{
std::cout << "- Partial solutions so far: " << solutions.size() << "\n";
std::vector<partial> next;
for(std::set<partial>::iterator it=solutions.begin();
it!=solutions.end(); ++it )
{
compute_partials( next, *it );
}
solutions.clear();
for(int j=0; j<next.size(); ++j)
{
if( unique( next[j] ) )
solutions.insert( next[j] );

}
}

std::cout << "\n" << solutions.size() << " fundamental solutions found: \n\n";
std::cout.flush();
std::set<partial>::iterator it;
int solno=1;
for(it=solutions.begin(); it!=solutions.end(); it++)
{
std::cout << "Solution #" << solno++ << "\n";
print_solution(*it);
if( solno <= solutions.size() )
{
std::cout << "\nPress enter to see the next solution.\n";
std::cin.get();
}
}
std::cout << "\nThanks for checking it out.\n\nPeace.";
}

```

### 0 Comments On This Entry

There are no Trackbacks for this entry

S M T W T F S
12
3456789
10111213141516
17181920 21 2223
24252627282930
31