This can definitely be optimized. First, though, a few style points. Don't use #define N
as Hosch250 says. Jamal points out to use std:array
; this can make some later aspects nicer, too.
Sort your imports. Don't use using namespace std
. I'm not sure why you imported cstdio
or cstdlib
... so don't. Space your operators, even <<
. Use braces around all blocks.
This:
if (x == true)
if (x == false)
should be
if (x)
if (!x)
Be consistent with spacing (eg. don't add spacing inside brackets in only one place). Use const
in printSolution
.
Remove return 0
from main
and the useless // Main
comment. Similarly for the /* print solution */
comment. I'm personally not a fan of /* this comment style */
although I admit that's particularly subjective.
I'd rename printSolution
to printBoard
, since it doesn't require a solution.
Convert int
s to bool
s where appropriate.
You should use ++i
and --i
over the postfix forms by convention.
Now the tiny things are out of the way, consider improving printSolution
with range-based for
loops:
void printSolution(const std::array<std::array<int, N>, N> &board)
{
for (auto row : board)
{
for (auto val : row)
{
std::cout << val << " ";
}
std::cout << std::endl;
}
}
Consider giving a better description of isSafe
and what it assumes:
// Check if a queen can be placed at (row, col)
// This assumes that there is exactly one queen in each column
// less than col and none in any other.
This can be simplified by compressing the array
to a 1-dimensional array of integers, since we know that the positions are bounded to one-per-column. This speeds up isSafe
, improving timings.
It looks like this:
#include <array>
#include <iostream>
const int N = 25;
void printBoard(const std::array<int, N> &board)
{
for (int i = 0; i < board.size(); ++i)
{
for (auto val : board)
{
std::cout << (val == i) << " ";
}
std::cout << std::endl;
}
}
// Check if a queen can be placed at (row, col)
// This assumes that there is exactly one queen in each column
// less than col and none in any other.
bool isSafe(std::array<int, N> &board, int row, int col)
{
for (int i = 1; i <= col; ++i)
{
if (board[col-i] == row)
{
return false;
}
// Up diagonal
if (board[col-i] == row - i)
{
return false;
}
// Down diagonal
if (board[col-i] == row + i)
{
return false;
}
}
return true;
}
bool solveNQRecurse(std::array<int, N> &board, int col)
{
if (col >= N)
{
return true;
}
for (int i = 0; i < N; ++i)
{
if (isSafe(board, i, col))
{
board[col] = i;
if (solveNQRecurse(board, col + 1))
{
return true;
}
}
}
return false;
}
/* solves the N Queen problem using Backtracking.*/
bool solveNQ()
{
std::array<int, N> board{};
if (!solveNQRecurse(board, 0))
{
std::cout << "Solution does not exist" << std::endl;
return false;
}
printBoard(board);
return true;
}
int main()
{
solveNQ();
}
The next thing to do is optimize isSafe
by converting it to a bitset. Since it will be useful later, I will use an uint64_t
instead of an std::bitset
; this is fine since a 65x65 grid won't be quickly solvable anyway. The idea is expressed in the Java version of this question; you keep track of three masks of which diagonals and rows are free. You then shift these and combine them with &
. This makes isSafe
just
bool isSafe(uint64_t rowsFree, uint64_t upDiagFree, uint64_t downDiagFree, uint64_t col) {
return (rowsFree & upDiagFree & downDiagFree) & (1ULL << col);
}
However, there's a special trick to just enumerate the set bits in a value, making this unneeded. I'll just convert the code from the Java version, since it's what I'd get to anyway.
This optimization takes it from a good 23 seconds for N=30 to to just 0.36; or a speed improvement of almost 100x. This gives
#include <array>
#include <bitset>
#include <iostream>
uint64_t const N = 30;
void printBoard(std::array<uint64_t, N> const &board)
{
for (uint64_t i = 0; i < N; ++i)
{
for (auto val : board)
{
std::cout << (val == (1 << i) ? "♛" : "·") << " ";
}
std::cout << std::endl;
}
}
// Use bit hackery to extract lowest bit from spaces,
// mutating both.
void splitLowestBit(uint64_t &bits, uint64_t &bit) {
// Copy all of the bits
bit = bits;
// Remove the lowest bit from the original
bits &= bits - 1ULL;
// Remove the rest of the bits from the copy
bit ^= bits;
}
bool solveNQRecurse(
std::array<uint64_t, N> &board,
uint64_t const rowsFree,
uint64_t const upDiagFree,
uint64_t const downDiagFree,
uint64_t const col
)
{
if (!rowsFree) {
return true;
}
uint64_t spaces = rowsFree & upDiagFree & downDiagFree;
while (spaces)
{
uint64_t bit;
splitLowestBit(spaces, bit);
board[col] = bit;
bool solvable = solveNQRecurse(
board,
(bit ^ rowsFree),
((bit ^ upDiagFree) >> 1ULL) | (1ULL << N),
((bit ^ downDiagFree) << 1ULL) | 1ULL,
col + 1ULL
);
if (solvable) { return true; }
}
return false;
}
/* solves the N Queen problem using Backtracking.*/
bool solveNQ()
{
std::array<uint64_t, N> board{};
uint64_t fullMask = (1ULL << N) - 1ULL;
bool solvable = solveNQRecurse(
board, // board
fullMask, // rowsFree
fullMask, // upDiagFree
fullMask, // downDiagFree
0 // col
);
if (solvable)
{
printBoard(board);
}
else
{
std::cout << "Solution does not exist" << std::endl;
}
return solvable;
}
int main()
{
solveNQ();
}