Chess puzzle improvement

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

#include 
#include 
#include 
#define N 10
using namespace std;

/* print solution */
void printSolution(int board[N][N])
{
    for (int i = 0; i = 0 && j >= 0; i--, j--)
    {
        if (board[i][j])
            return false;
    }

    for (i = row, j = col; j >= 0 && i = N)
        return true;
    for (int i = 0; i < 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<<"Solution does not exist"<<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 <<. 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, 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 
#include 

const int N = 25;

void printBoard(const std::array &board)
{
    for (int i = 0; i  &board, int row, int col)
{   
    for (int i = 1; i  &board, int col)
{
    if (col >= N)
    {
        return true;
    }
    for (int i = 0; i  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 
#include 
#include 

uint64_t const N = 30;

void printBoard(std::array const &board)
{
    for (uint64_t i = 0; i  &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  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();
}

StackExchange Code Review Q#77669, answer score: 7