8
\$\begingroup\$

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

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define N 10
using namespace std;

/* print solution */
void printSolution(int board[N][N])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            cout<<board[i][j]<<"  ";
        cout<<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 < col; i++)
    {
        if (board[row][i])
            return false;
    }
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j])
            return false;
    }

    for (i = row, j = col; j >= 0 && i < 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 >= 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;
}
\$\endgroup\$
1
  • 6
    \$\begingroup\$ Welcome to Code Review! When asking this type of questions, it is often a good idea to add a short description about how your approach works, that often makes the code easier to follow for reviewers. \$\endgroup\$ Jan 16, 2015 at 1:22

3 Answers 3

7
\$\begingroup\$

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<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();
}
\$\endgroup\$
3
  • \$\begingroup\$ How does exactly work printBoard function which is given after first optimization of isSafe function? \$\endgroup\$
    – Marci
    Jan 18, 2015 at 21:03
  • \$\begingroup\$ Occasionally, I do prefer if (x == true) when x is an expression that just sounds like a boolean value rather than something resembling the answer to a question. It's a tossup whether solveNQUtil(...) sounds like a question.... \$\endgroup\$
    – user14393
    Mar 13, 2015 at 10:21
  • \$\begingroup\$ @Hurkyl In that case you'd be using true and false as a 2-state enum where true and false aren't actually valid values. You should replace it with something that is semantically meaningful. In this case, solveNQ is merely misnamed, but this is because it prints its value instead of returning it (which in some sense is the real problem). \$\endgroup\$
    – Veedrac
    Mar 13, 2015 at 12:07
6
\$\begingroup\$

One huge problem you have here is #define N 10. This is not at all what you should be doing here; this is where a const int should be used. #define should never be used like this.

const int N = 10;

A second problem is that while this is a small program, you should still use more descriptive names: N should maybe be BoardSize.


I wonder why you have i and j defined with function scope in isSafe()? You always give them a starting value in the loops, so you should make them have loop scope:

for (int i = row, j = col; j >= 0 && i < N; i++, j--)
{
    if (board[i][j])
        return false;
}

And finally, once you get more advanced, you may find it a problem to declare using namespace std; because of overlapping definitions, so the compiler doesn't know which to use. Most C++ programmers do not do this, but explicitly state std:: instead. This is mentioned more in-depth here.


I do not know if this can be optimized, but it looks extremely simple already; also, I ran it with N = 25 at Ideone, and it finished it in less than a second. I doubt it needs optimizing.

\$\endgroup\$
4
\$\begingroup\$

Passing C-arrays to functions is not good to do in C++. Doing so causes them to decay to pointers and can lead to some problems. Instead, use a container such as std::array. Using these with functions involves passing around an instance of this container, which is much safer to do. Everything related to memory is handled by the class internally.

Your 2D board (zero-initialized) should look like this:

std::array<std::array<int, N>, N> board{};

Accessing indices is still done the same way, but you now have access to various member functions for this class, such as size().

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.