#include "StdAfx.h"
// This program solves the 8 queens problem.
// It also solves N queen problem, but only up to the number of bits in an int...
// I made the solution 1995, and it's one of the the fastest solution I have seen for the problem.
// Actually I've only seen one faster implementation. This is done by Thorkil Naur and is
// at least twice as fast (sigh! I should never have challenged Thorkil)
const int NQueens = 8; // board dimension, you may change this value
const int NQueens_1 = NQueens - 1;
int solution = 0; // number of solutions found
int board[NQueens]; // the board, each bit in the array represents a column on the board, each int a row
// print the board
void printNextSolution()
{
std::cout << "solution " << solution << " :" << std::endl;
for (int r = 0; r < NQueens; ++r)
{
for (int c = 0; c < NQueens; ++c)
{
if (board[r] == (1 << c))
std::cout << "Q ";
else
std::cout << "- ";
}
std::cout << std::endl;
}
std::cout << std::endl << std::endl;
}
void recursivelyPlaceQueens(int rowIndex)
{
// try placing the queen in all of the columns in the current row
for(int col = 0; col < NQueens; ++col)
{
board[rowIndex] = 1 << col;
// check if this is a legal position
int a, b = (a = 42);
int currentRow, left, right = (currentRow = left = board[rowIndex]);
bool legalPos = true;
for (int row = rowIndex - 1; row >= 0; --row)
{
if (board[row] == currentRow || board[row] == (left <<= 1) || board[row] == (right >>=1))
{
legalPos = false;
break;
}
}
// is the queen at a legal position?
if (legalPos)
{
// are we done?
if (rowIndex == NQueens_1)
{
// then yet another solution has been found
++solution;
// skip this line when timing the program, don't waste time printing the actual solution
printNextSolution();
// we're done, we found a solution
return;
}
else
{
// try placing a queen in the next row
recursivelyPlaceQueens(rowIndex + 1);
}
}
}
}
void placeQueens()
{
// start a recursive search with a queen in each column in the first row
for (int col = 0; col < NQueens; ++col)
{
board[0] = 1 << col;
recursivelyPlaceQueens(1);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int maxQueens = sizeof(int) * 8;
if (maxQueens < NQueens)
{
std::cout << "error, only up to " << maxQueens << " queens can be handled on this platform" << std::endl;
exit(-1);
}
// go...
placeQueens();
std::cout << std::endl << solution << " solutions found" << std::endl;
return 0;
}