C++: N-Queens Problem

// Much shorter than the version below;
// uses C++11 threads to parallelize the computation; also uses backtracking
// Outputs all solutions for any table size
#include <vector>
#include <iostream>
#include <iomanip>
#include <thread>
#include <future>

// Print table. 'pos' is a vector of positions – the index in pos is the row,
// and the number at that index is the column where the queen is placed.
static void print(const std::vector<int> &pos)
{
	// print table header
	for (int i = 0; i < pos.size(); i++) {
		std::cout << std::setw(3) << char('a' + i);
	}

	std::cout << '\n';

	for (int row = 0; row < pos.size(); row++) {
		int col = pos[row];
		std::cout << row + 1 << std::setw(3 * col + 3) << " # ";
		std::cout << '\n';
	}

	std::cout << "\n\n";
}

static bool threatens(int row_a, int col_a, int row_b, int col_b)
{
	return row_a == row_b // same row
	or col_a == col_b // same column
	or std::abs(row_a - row_b) == std::abs(col_a - col_b); // diagonal
}

// the i-th queen is in the i-th row
// we only check rows up to end_idx
// so that the same function can be used for backtracking and checking the final solution
static bool good(const std::vector<int> &pos, int end_idx)
{
	for (int row_a = 0; row_a < end_idx; row_a++) {
		for (int row_b = row_a + 1; row_b < end_idx; row_b++) {
			int col_a = pos[row_a];
			int col_b = pos[row_b];
			if (threatens(row_a, col_a, row_b, col_b)) {
				return false;
			}
		}
	}

	return true;
}

static std::mutex print_count_mutex; // mutex protecting 'n_sols'
static int n_sols = 0; // number of solutions

// recursive DFS backtracking solver
static void n_queens(std::vector<int> &pos, int index)
{
	// if we have placed a queen in each row (i. e. we are at a leaf of the search tree), check solution and return
	if (index >= pos.size()) {
		if (good(pos, index)) {
			std::lock_guard<std::mutex> lock(print_count_mutex);
			print(pos);
			n_sols++;
		}

		return;
	}

	// backtracking step
	if (not good(pos, index)) {
		return;
	}

	// optimization: the first level of the search tree is parallelized
	if (index == 0) {
		std::vector<std::future<void>> fts;
		for (int col = 0; col < pos.size(); col++) {
			pos[index] = col;
			auto ft = std::async(std::launch::async, [=]{ auto cpos(pos); n_queens(cpos, index + 1); });
			fts.push_back(std::move(ft));
		}

		for (const auto &ft : fts) {
			ft.wait();
		}
	} else { // deeper levels are not
		for (int col = 0; col < pos.size(); col++) {
			pos[index] = col;
			n_queens(pos, index + 1);
		}
	}
}

int main()
{
	std::vector<int> start(12); // 12: table size
	n_queens(start, 0);
	std::cout << n_sols << " solutions found.\n";
	return 0;
}

Output:

// A straight-forward brute-force C++ version with formatted output,
// eschewing obfuscation and C-isms, producing ALL solutions, which
// works on any OS with a text terminal.
//
// Two basic optimizations are applied:
//
//   It uses backtracking to only construct potentially valid solutions.
//
//   It only computes half the solutions by brute -- once we get the
//   queen halfway across the top row, any remaining solutions must be
//   reflections of the ones already computed.
//
// This is a bare-bones example, without any progress feedback or output
// formatting controls, which a more complete program might provide.
//
// Beware that computing anything larger than N=14 might take a while.
// (Time gets exponentially worse the higher the number.)

// Copyright 2014 Michael Thomas Greer
// Distributed under the Boost Software License, Version 1.0.
// http://www.boost.org/LICENSE_1_0.txt

#include <algorithm>
#include <ciso646>
#include <iomanip>
#include <iostream>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>


// ///////////////////////////////////////////////////////////////////////////
struct queens
/////////////////////////////////////////////////////////////////////////// //
{
	// TYPES -------------------------------------------------------------------

	// A row or column index. (May be signed or unsigned.)
	//
	typedef signed char index_type;

	// A 'solution' is a row --> column lookup of queens on the board.
	//
	// It has lexicographical order and can be transformed with a variety of
	// reflections, which, when properly combined, produce all possible
	// orientations of a solution.
	//
	struct solution_type: std::vector <index_type>
	{
		typedef std::vector <index_type> base_type;

		// constructors  . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
		solution_type( std::size_t N          ): base_type( N, -1 ) { }
		solution_type( const solution_type& s ): base_type( s     ) { }

		// compare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
		bool operator < ( const solution_type& s ) const
		{
			auto mm = std::mismatch( begin(), end(), s.begin() );
			return (mm.first != end()) and (*mm.first < *mm.second);
		}

		// transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . .
		void vflip() { std::reverse( begin(), end() ); }

		void hflip() { for (auto& x : *this) x = size() - 1 - x; }

		void transpose()
		{
			solution_type result( size() );
			for (index_type y = 0; (std::size_t)y < size(); y++)
			result[ (*this)[ y ] ] = y;
			swap( result );
		}
	};

	// MEMBER VALUES -----------------------------------------------------------

	const int                N;
	std::set <solution_type> solutions;

	// SOLVER ------------------------------------------------------------------

	queens( int N = 8 ):
	N( (N < 0) ? 0 : N )
	{
		// Row by row we create a potentially valid solution.
		// If a queen can be placed in a valid spot by the time
		// we get to the last row, then we've found a solution.

		solution_type solution( N );
		index_type row = 0;
		while (true)
		{
			// Advance the queen along the row
			++solution[ row ];

			// (If we get past halfway through the first row, we're done.)
			if ((row == 0) and (solution[ 0 ] > N/2)) break;

			if (solution[ row ] < N)
			{
				// If the queen is in a good spot...
				if (ok( solution, row, solution[ row ] ))
				{
					// ...and we're on the last row
					if (row == N-1)
					{
						// Add the solution we found plus all it's reflections
						solution_type
						s = solution;  solutions.insert( s );
						s.vflip();     solutions.insert( s );
						s.hflip();     solutions.insert( s );
						s.vflip();     solutions.insert( s );
						s.transpose(); solutions.insert( s );
						s.vflip();     solutions.insert( s );
						s.hflip();     solutions.insert( s );
						s.vflip();     solutions.insert( s );
					}
					// otherwise begin marching a queen along the next row
					else solution[ ++row ] = -1;
				}

				// When we get to the end of a row's columns then
				// we need to backup a row and continue from there.
			}
			else --row;
		}
	}

	// HELPER ------------------------------------------------------------------
	// This routine helps the solver by identifying column locations
	// that do not conflict with queens already placed in prior rows.

	bool ok( const solution_type& columns, index_type row, index_type column )
	{
		for (index_type r = 0; r < row; r++)
		{
			index_type c         = columns[ r ];
			index_type delta_row = row - r;
			index_type delta_col = (c < column) ? (column - c) : (c - column);

			if ((c == column) or (delta_row == delta_col))
			return false;
		}
		return true;
	}

	// OUTPUT A SINGLE SOLUTION ------------------------------------------------
	//
	// Formatted as (for example):
	//
	//   d1 b2 g3 c4 f5 h6 e7 a8
	//   Q - - - - - - -
	//   - - - - Q - - -
	//   - - - - - - - Q
	//   - - - - - Q - -
	//   - - Q - - - - -
	//   - - - - - - Q -
	//   - Q - - - - - -
	//   - - - Q - - - -
	//
	friend
	std::ostream&
	operator << ( std::ostream& outs, const queens::solution_type& solution )
	{
		static const char* squares[] = { "- ", "Q " };
		index_type N = solution.size();

		// Display the queen positions
		for (auto n = N; n--; )
		outs << (char)('a' + solution[ n ]) << (N - n) << " ";

		// Display the board
		for (auto queen : solution)
		{
			outs << "\n";
			for (index_type col = 0; col < N; col++)
			outs << squares[ col == queen ];
		}
		return outs;
	}

	// OUTPUT ALL SOLUTIONS ----------------------------------------------------
	//
	// Display "no solutions" or "N solutions" followed by
	// each individual solution, separated by blank lines.

	friend
	std::ostream&
	operator << ( std::ostream& outs, const queens& q )
	{
		if (q.solutions.empty()) outs << "no";
		else                     outs << q.solutions.size();
		outs << " solutions";

		std::size_t n = 1;
		for (auto solution : q.solutions)
		{
			outs << "\n\n#" << n++ << "\n" << solution;
		}

		return outs;
	}
};


/* ///////////////////////////////////////////////////////////////////////////
string_to <type> ( x )
/////////////////////////////////////////////////////////////////////////// */

template <typename T>
T string_to( const std::string& s )
{
	T result;
	std::istringstream ss( s );
	ss >> result;
	if (!ss.eof()) throw std::runtime_error( "to_string(): invalid conversion" );
	return result;
}

template <typename T, T default_value>
T string_to( const std::string& s )
{
	try { return string_to <T> ( s ); }
	catch (...) { return default_value; }
}


/* ///////////////////////////////////////////////////////////////////////////
main program
/////////////////////////////////////////////////////////////////////////// */

int usage( const std::string& name )
{
	std::cerr <<
	"usage:\n  " << name << " 8\n\n"
	""
	"Solve the N-Queens problem, brute-force,\n"
	"and show all solutions for an 8x8 board.\n\n"
	""
	"(Specify a value other than 8 for the board size you want.)\n";
	return 1;
}

int main( int argc, char** argv )
{
	signed N =
	(argc < 2) ? 8 :
	(argc > 2) ? 0 : string_to <signed, 0> ( argv[ 1 ] );

	if (N <= 0) return usage( argv[ 0 ] );

	std::cout << queens( N ) << "\n";
}

Output:

#include <windows.h>
#include <iostream>
#include <string>

//--------------------------------------------------------------------------------------------------
using namespace std;

//--------------------------------------------------------------------------------------------------
class point
{
public:
	int x, y;
	point(){ x = y = 0; }
	void set( int a, int b ){ x = a; y = b; }
};
//--------------------------------------------------------------------------------------------------
class nQueens
{
public:
	void solve( int c )
	{
		_count = c; int len = ( c + 1 ) * ( c + 1 ); _queens = new bool[len]; memset( _queens, 0, len );
		_cl = new bool[c]; memset( _cl, 0, c ); _ln = new bool[c]; memset( _ln, 0, c );
		point pt; pt.set( rand() % c, rand() % c ); putQueens( pt, c ); displayBoard();
		delete [] _queens; delete [] _ln; delete [] _cl;
	}

private:
	void displayBoard()
	{
		system( "cls" ); string t = "+---+", q = "| Q |", s = "|   |";
		COORD c = { 0, 0 }; HANDLE h = GetStdHandle( STD_OUTPUT_HANDLE );
		for( int y = 0, cy = 0; y < _count; y++ )
		{
			int yy = y * _count;
			for( int x = 0; x < _count; x++ )
			{
				SetConsoleCursorPosition( h, c ); cout << t;
				c.Y++; SetConsoleCursorPosition( h, c );
				if( _queens[x + yy] ) cout << q; else cout << s;
				c.Y++; SetConsoleCursorPosition( h, c );
				cout << t; c.Y = cy; c.X += 4;
			}
			cy += 2; c.X = 0; c.Y = cy;
		}
	}

	bool checkD( int x, int y, int a, int b )
	{
		if( x < 0 || y < 0 || x >= _count || y >= _count ) return true;
		if( _queens[x + y * _count] ) return false;
		if( checkD( x + a, y + b, a, b ) ) return true;
		return false;
	}

	bool check( int x, int y )
	{
		if( _ln[y] || _cl[x] )        return false;
		if( !checkD( x, y, -1, -1 ) ) return false;
		if( !checkD( x, y,  1, -1 ) ) return false;
		if( !checkD( x, y, -1,  1 ) ) return false;
		if( !checkD( x, y,  1,  1 ) ) return false;
		return true;
	}

	bool putQueens( point pt, int cnt )
	{
		int it = _count;
		while( it )
		{
			if( !cnt ) return true;
			if( check( pt.x, pt.y ) )
			{
				_queens[pt.x + pt.y * _count] = _cl[pt.x] = _ln[pt.y] = true;
				point tmp = pt; if( ++tmp.x >= _count ) tmp.x = 0; if( ++tmp.y >= _count ) tmp.y = 0;
				if( putQueens( tmp, cnt - 1 ) ) return true;
				_queens[pt.x + pt.y * _count] = _cl[pt.x] = _ln[pt.y] = false;
			}
			if( ++pt.x >= _count ) pt.x = 0;
			it--;
		}
		return false;
	}

	int          _count;
	bool*        _queens, *_ln, *_cl;
};
//--------------------------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
	nQueens n; int nq;
	while( true )
	{
		system( "cls" ); cout << "Enter board size bigger than 3 (0 - 3 to QUIT): "; cin >> nq;
		if( nq < 4 ) return 0; n.solve( nq ); cout << endl << endl;
		system( "pause" );
	}
	return  0;
}
//--------------------------------------------------------------------------------------------------

Output:

#include <windows.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

//--------------------------------------------------------------------------------------------------
using namespace std;

//--------------------------------------------------------------------------------------------------
typedef unsigned int uint;

//--------------------------------------------------------------------------------------------------
class nQueens_Heuristic
{
public:
	void solve( uint n ) { makeList( n ); drawBoard( n ); }

private:
	void drawBoard( uint n )
	{
		system( "cls" ); string t = "+---+", q = "| Q |", s = "|   |";
		COORD c = { 0, 0 }; HANDLE h = GetStdHandle( STD_OUTPUT_HANDLE );
		uint w = 0;
		for( uint y = 0, cy = 0; y < n; y++ )
		{
			for( uint x = 0; x < n; x++ )
			{
				SetConsoleCursorPosition( h, c ); cout << t;
				c.Y++; SetConsoleCursorPosition( h, c );
				if( x + 1 == solution[w] ) cout << q; else cout << s;
				c.Y++; SetConsoleCursorPosition( h, c );
				cout << t; c.Y = cy; c.X += 4;
			}
			cy += 2; c.X = 0; c.Y = cy; w++;
		}
		solution.clear(); odd.clear(); evn.clear();
	}

	void makeList( uint n )
	{
		uint r = n % 6;
		for( uint x = 1; x <= n; x++ )
		{
			if( x & 1 ) odd.push_back( x );
			else evn.push_back( x );
		}
		if( r == 2 )
		{
			swap( odd[0], odd[1] );
			odd.erase( find( odd.begin(), odd.end(), 5 ) );
			odd.push_back( 5 );
		}
		else if( r == 3 )
		{
			odd.erase( odd.begin() ); odd.erase( odd.begin() );
			odd.push_back( 1 ); odd.push_back( 3 );
			evn.erase( evn.begin() ); evn.push_back( 2 );
		}
		vector<uint>::iterator it = evn.begin();
		while( it != evn.end() ) 
		{
			solution.push_back( ( *it ) );
			it++;
		}
		it = odd.begin();
		while( it != odd.end() ) 
		{
			solution.push_back( ( *it ) );
			it++;
		}
	}

	vector<uint> odd, evn, solution;
};
//--------------------------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
	uint n; nQueens_Heuristic nQH;
	while( true )
	{
		cout << "Enter board size bigger than 3 (0 - 3 to QUIT): "; cin >> n;
		if( n < 4 ) return 0;
		nQH.solve( n ); cout << endl << endl;
	}
	return 0;
}
//--------------------------------------------------------------------------------------------------