Chess puzzle improvement Is it possible to optimize this solution to the N-queens puzzle?

#include &lt;iostream&gt;
#include &lt;cstdio&gt;
#include &lt;cstdlib&gt;
#define N 10
using namespace std;

/* print solution */
void printSolution(int board[N][N])
{
    for (int i = 0; i &lt; N; i++)
    {
        for (int j = 0; j &lt; N; j++)
            cout&lt;&lt;board[i][j]&lt;&lt;"  ";
        cout&lt;&lt;endl;
    }
}

/* check if a queen can be placed on board[row][col]*/
bool isSafe(int board[N][N], int row, int col)
{
    int i, j;
    for (i = 0; i &lt; col; i++)
    {
        if (board[row][i])
            return false;
    }
    for (i = row, j = col; i &gt;= 0 &amp;&amp; j &gt;= 0; i--, j--)
    {
        if (board[i][j])
            return false;
    }

    for (i = row, j = col; j &gt;= 0 &amp;&amp; i &lt; N; i++, j--)
    {
        if (board[i][j])
            return false;
    }

    return true;
}

/*solve N Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
    if (col &gt;= N)
        return true;
    for (int i = 0; i &lt; N; i++)
    {
        if ( isSafe(board, i, col) )
        {
            board[i][col] = 1;
            if (solveNQUtil(board, col + 1) == true)
                return true;
            board[i][col] = 0;
        }
    }
    return false;
}

/* solves the N Queen problem using Backtracking.*/
bool solveNQ()
{
    int board[N][N] = {0};
    if (solveNQUtil(board, 0) == false)
    {
        cout&lt;&lt;"Solution does not exist"&lt;&lt;endl;
        return false;
    }
    printSolution(board);
    return true;
}

// Main
int main()
{
    solveNQ();
    return 0;
}
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 &lt;&lt;. 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 ints to bools 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&lt;std::array&lt;int, N&gt;, N&gt; &amp;board)
{
    for (auto row : board)
    {
        for (auto val : row)
        {
            std::cout &lt;&lt; val &lt;&lt; "  ";
        }
        std::cout &lt;&lt; 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 &lt;array&gt;
#include &lt;iostream&gt;

const int N = 25;

void printBoard(const std::array&lt;int, N&gt; &amp;board)
{
    for (int i = 0; i &lt; board.size(); ++i)
    {
        for (auto val : board)
        {
            std::cout &lt;&lt; (val == i) &lt;&lt; "  ";
        }
        std::cout &lt;&lt; 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&lt;int, N&gt; &amp;board, int row, int col)
{   
    for (int i = 1; i &lt;= 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&lt;int, N&gt; &amp;board, int col)
{
    if (col &gt;= N)
    {
        return true;
    }
    for (int i = 0; i &lt; 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&lt;int, N&gt; board{};
    if (!solveNQRecurse(board, 0))
    {
        std::cout &lt;&lt; "Solution does not exist" &lt;&lt; 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 &amp;. This makes isSafe just

bool isSafe(uint64_t rowsFree, uint64_t upDiagFree, uint64_t downDiagFree, uint64_t col) {
    return (rowsFree &amp; upDiagFree &amp; downDiagFree) &amp; (1ULL &lt;&lt; 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 &lt;array&gt;
#include &lt;bitset&gt;
#include &lt;iostream&gt;

uint64_t const N = 30;

void printBoard(std::array&lt;uint64_t, N&gt; const &amp;board)
{
    for (uint64_t i = 0; i &lt; N; ++i)
    {
        for (auto val : board)
        {
            std::cout &lt;&lt; (val == (1 &lt;&lt; i) ? "♛" : "·") &lt;&lt; " ";
        }
        std::cout &lt;&lt; std::endl;
    }
}

// Use bit hackery to extract lowest bit from spaces,
// mutating both.
void splitLowestBit(uint64_t &amp;bits, uint64_t &amp;bit) {
    // Copy all of the bits
    bit = bits;

    // Remove the lowest bit from the original
    bits &amp;= bits - 1ULL;

    // Remove the rest of the bits from the copy
    bit ^= bits;
}

bool solveNQRecurse(
    std::array&lt;uint64_t, N&gt; &amp;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 &amp; upDiagFree &amp; downDiagFree;

    while (spaces)
    {
        uint64_t bit;
        splitLowestBit(spaces, bit);
        board[col] = bit;

        bool solvable = solveNQRecurse(
            board,
            (bit ^ rowsFree),
            ((bit ^ upDiagFree) &gt;&gt; 1ULL) | (1ULL &lt;&lt; N),
            ((bit ^ downDiagFree) &lt;&lt; 1ULL) | 1ULL,
            col + 1ULL
        );

        if (solvable) { return true; }
    }
    return false;
}

/* solves the N Queen problem using Backtracking.*/
bool solveNQ()
{
    std::array&lt;uint64_t, N&gt; board{};
    uint64_t fullMask = (1ULL &lt;&lt; N) - 1ULL;

    bool solvable = solveNQRecurse(
        board,      // board
        fullMask,   // rowsFree
        fullMask,   // upDiagFree
        fullMask,   // downDiagFree
        0           // col
    );

    if (solvable)
    {
        printBoard(board);
    }
    else
    {
        std::cout &lt;&lt; "Solution does not exist" &lt;&lt; std::endl;
    }

    return solvable;
}

int main()
{
    solveNQ();
}