UVA 750: 8 Queens Chess

Question

In chess it is possible to place eight queens on the board so that no one queen can be taken by any other. Write a program that will determine all such possible arrangements for eight queens given the initial position of one of the queens.

Input

The first line of the input contains the number of datasets, and it's followed by a blank line. Each dataset contains a pair of positive integers separated by a single space that describes the initial position of one of the 8 queens

Output

Output for each dataset will consist of a one-line-per-solution representation.

Each solution will be sequentially numbered 1...N. Each solution will consist of 8 numbers. Each of the 8 numbers will be the ROW coordinate for that solution. The column coordinate will be indicated by the order in which the 8 numbers are printed. That is, the rst number represents the ROW in which the queen is positioned in column 1; the second number represents the ROW in which the queen is positioned in column 2, and so on

Sample Input

1

1 1

Sample Output

SOLN       COLUMN  
 #     1 2 3 4 5 6 7 8  

 1     1 5 8 6 3 7 2 4  
 2     1 6 8 3 7 4 2 5  
 3     1 7 4 6 8 2 5 3  
 4     1 7 5 8 2 4 6 3

The full description of the problem can be found here.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

class Chess
{
    const int row_size, col_size;
    const int row_queen, col_queen;
    std::vector<std::vector<int> > sol;
    // queens_row_num[i] == on which row the queen is placed on col i
    int queens_row_num[8 + 1], idx_queens_row_num;

    bool queen_is_in_attack_pos(const int &row, const int &col)
    {
        for ( int j = 1; j <= col_size; ++j )
        {
            if ( queens_row_num[j] )
        {
            if ( std::abs(queens_row_num[j] - row) ==
             std::abs(j - col) ||
             queens_row_num[j] == row || j == col )
            return true;
        }
        }
        return false;
    }

    bool eight_queens_are_in_place()
    {
        for ( int j = 1; j <= col_size; ++j )
        {
        if ( !queens_row_num[j] )
                return false;
        }
        return true;
    }

    void store_cur_sol()
    {
        std::vector<int> v;
        for ( int j = 1; j <= col_size; ++j )
        {
        v.push_back(queens_row_num[j]);
        }
        sol.push_back(v);
    }

    void go_through_board(int col)
    {

        if ( eight_queens_are_in_place() )
        {
        store_cur_sol();
            return;
        }
        for ( int j = col + 1; j <= col_size; ++j )
        {
        if ( queens_row_num[j] )
            continue;
        for ( int i = 1; i <= row_size; ++i )
        {
            if ( !queen_is_in_attack_pos(i, j) )
            {
            queens_row_num[j] = i;
            go_through_board(j);
            queens_row_num[j] = 0;
            }
        }
        }
    }
public:
    Chess(const int &r, const int &c) : row_queen(r), col_queen(c),
                                        row_size(8), col_size(8)
    {}

    void find_solutions()
    {
        // go through the column so as to get the solution
        // in sorted order

        std::fill(queens_row_num, queens_row_num + col_size + 1, 0);
        queens_row_num[col_queen] = row_queen;
        go_through_board(0);
    }

    void print_solutions()
    {
        std::cout << "SOLN       COLUMN" << std::endl;
        std::cout << " #      1 2 3 4 5 6 7 8" << std::endl;
        std::cout << std::endl;

        for ( int i = 1; i <= (int)sol.size(); ++i )
        {
        std::cout << (i < 10 ? " " : "") << i << "     ";
            for ( int k = 0; k < col_size; ++k )
        {
            std::cout << " " << sol[i - 1][k];
        }
        std::cout << std::endl;
        }
    }
};

int main()
{
    int T;

    std::cin >> T;
    for ( int t = 1; t <= T; ++t )
    {
        int r, c;
        std::cin >> r >> c;
        Chess chess = Chess(r, c);

        chess.find_solutions();
        chess.print_solutions();
        if ( t < T )
            std::cout << std::endl;
    }
    return 0;
}

What are the possible way to improve:

• on quality-wise
• to make it more readable so that someone can understand 6 months down the road
• to make it more C++-like

Answer 1

Besides what Hosch250 said, with all of which I agree, here are a few more C++ style points:

---

#include <cmath>

You don't use anything from <cmath>, but you do use std::abs, which is located in <cstdlib>.

---

const int row_size, col_size;
const int row_queen, col_queen;

It is generally considered bad style to declare multiple entities on the same line. Consider:

int const *a, b;   // what is the type of "b"?

Also, I see you're declaring these non-static data members as const. This is mostly harmless in C++03, but I strongly advise you to break the habit now.

• A class with const data members of primitive type will not have a default constructor implicitly defined, which means its default constructor cannot be trivial.

• A class with const data members generally cannot appear on the LHS of an assignment; that is, you can't meaningfully assign-into it if part of its value is immutable. This hurts the pursuit of value semantics in general.

• A class with const data members can appear on the RHS of an assignment, or be returned from a function, but its implicitly generated move constructor will have to copy the const members instead of moving them, since they're not allowed to be modified.

Notice that the first bullet point applies only to const data members of primitive type, and the third bullet point applies only to const data members of complicated types. The second bullet point always applies, though.

Bottom line: Prefer to let your user determine the constness of his own variables, e.g. const Chess c(1,1); means that all the members of c are const, and Chess nc(1,1); means that none of them are. And the assignment nc = c; should Just Work.

---

bool queen_is_in_attack_pos(const int &row, const int &col)

Passing ints by const reference is weird. Anything register-sized or smaller, but especially primitive types like int, should be passed by value. The only reason to add the extra indirection of pass-by-reference is if it might be cheaper than making a copy of the value.

Also, almost all of these member functions should be qualified with const:

bool queen_is_in_attack_pos(int row, int col) const

since they don't mutate the Chess object in question.

---

void store_cur_sol()
{
    std::vector<int> v;
    for ( int j = 1; j <= col_size; ++j )
    {
    v.push_back(queens_row_num[j]);
    }
    sol.push_back(v);
}

I know you said C++03 not C++11-or-later, but just note in passing that in C++11-or-later you'd be writing sol.push_back(std::move(v)) instead of making a copy of v here. In C++03, to get the same level of performance, you might do something like

    sol.push_back(std::vector<int>());
    std::vector<int>& v = sol.back();
    v.resize(col_size);
    for ( int j = 1; j <= col_size; ++j )
    {
        v[j-1] = queens_row_num[j];
    }

(that is, construct the vector in the right place to begin with, instead of constructing it elsewhere and moving it into place).

---

Chess(const int &r, const int &c) // ...

void find_solutions() // ...

void print_solutions() // ...

Remind me why these are three separate member functions? If the only possible thing you can do with a Chess is to ask it for its list of solutions, then I don't see why the find_solutions method exists. It smells of two-phase initialization: first the user constructs the object, and then the user goes, "Oh shoot, I also need to do X before this object is safe to use!"

A better design would completely initialize the object in its constructor.

Furthermore, the print_solutions method is either inappropriate or incompletely parameterized. To see why: Suppose I gave you the exact same problem statement, but this time I wanted the solutions printed to std::cerr.

Better interfaces would include

void print_solutions(std::ostream& out) const;  // still bad

void for_each_solution(const boost::function<void(Solution)>& f) const;  // overkill

std::vector<Solution> get_solutions() const;  // probably best

---

So now we have a Chess class that's only safe to use like this:

Chess c(1,1);
std::vector<Solution> sols = c.get_solutions();

This continues to smell like two-phase initialization! So we refactor again and find out that we never needed the class in the first place.

std::vector<Solution> sols = get_solutions_for_chess_problem(1,1);

I encourage you to try rewriting the program in a completely procedural style (no OO) and see which way you like better.

---

Oh, and actually I disagree with one thing Hosch250 said. Go ahead and use std::endl. In toy code like this, the efficiency hit doesn't matter because your program is done in milliseconds anyway. In real code, the efficiency hit doesn't matter because your program isn't spending any of its running time on I/O. In fact, I doubt you'll see std::cout popping up in any real-world C++ codebases. But in simple programs like this, go ahead and use std::cout << "hello world" << std::endl; and don't listen to the people who say it should be std::cout << "hello world" << '\n'; for speed. ;) (And this is coming from a guy who'd write puts("hello world"); in his own code.)

Answer 2

First, your indentation is a little crazy, which makes it very difficult to see which code is in which scope. Consider:

   if ( queens_row_num[j] )
{
    if ( std::abs(queens_row_num[j] - row) ==
     std::abs(j - col) ||
     queens_row_num[j] == row || j == col )
    return true;
}

compared to:

if (queens_row_num[j])
{
    if (std::abs(queens_row_num[j] - row) == std::abs(j - col) ||
        queens_row_num[j] == row ||
        j == col)
    {
        return true;
    }
}

• I made each scope get its own indentation level.
• I gave each scope its own braces, which helps prevent bugs--especially important when working with improperly indented code.
• I put each part of the condition in the second if on its own line, with the boolean || operator at the end of the line. I always structure my ifs like this when the lines get too long. I split at the |, ||, &, &&, and ^ operators, but not the == operator or arithmetic/concatenation operators.
• This is purely stylistic, but I removed the spaces from the inside of the braces. You are pretty consistent about this, but have a few deviations. Consistency is more important here than the specific style you choose.

Notice how my version is easier to see what code is in what scope and executes when because you don't have to figure out what closing parenthesis and brace goes with which opening parenthesis and brace.

---

Overall, your naming is pretty good. print_solutions is an excellent name, but T, t, r, and c in main aren't so good. I assume the r and c stand for row and column? Why not name them that directly?

---

No using namespace std? Congratulations for not falling into that trap.

---

Using std::endl will flush the IO buffer, which ensures every character is printed before it lets you continue, and is a very expensive operation. You should just use \n (or System.Environment.NewLine if you are using Visual C++), and only flush the buffer at the end of the method, if necessary.

---

I have mixed feelings about this ctor:

Chess(const int &r, const int &c) : row_queen(r), col_queen(c),
                                    row_size(8), col_size(8)
{}

I like that you are setting the row size and column size in the ctor, which has a flavor of Dependency Injection and an extensible design; you can change those values to 10 and 10, and solve the more generic N-Queens problem very simply. The problem is that you hard-code the values in without giving the caller a chance to say which version they want solved; you should make these parameters for the caller to specify. Because the 8-Queens problem is the most common variant of the N-Queens, these parameters could be optional, which would let the caller solve the 8-Queens problem by creating:

Chess chess = Chess(setRow, setColumn);

and the N-Queens problem by calling:

Chess chess = Chess(setRow, setColumn, rows, columns);

Answer 3

Extraneous loop = massive waste of time

This loop in go_through_board():

    for ( int j = col + 1; j <= col_size; ++j )

is not necessary and in fact wastes a lot of time. You only have to work on col + 1, not every column. Once j becomes col + 2, all further computation at that point is wasted because you have skipped column col + 1 (you didn't place a queen there). Therefore, once you get to the last column and check eight_queens_in_place(), it will always return false because there is a queen missing from column col+1.

This loop also affects every level of recursion. The topmost call spends 7x as much time as required. The next level spends 6x. The next level spends 5x, etc. You probably didn't even notice the slowdown because the program finishes in a split second even with the wasted time. That is because the 8x8 problem doesn't require much computation to begin with. I modified your program to solve for a 13x13 board to illustrate the difference. The results:

Original program (13x13 board): 54 seconds
Fixed    program (13x13 board): 0.15 seconds

Fixed version

Here is the code for the fixed version of go_through_board(). Also notice that there is no longer a eight_queens_in_place() function because it is no longer needed.

void go_through_board(int col)
{
    // Advance to the next unsolved column.
    col++;
    if (queens_row_num[col]) {
        col++;
    }

    // If we reached the last column, we have found a solution.
    if (col > col_size) {
        store_cur_sol();
        return;
    }

    // Otherwise, try placing a queen somewhere in this column and recurse.
    for (int i = 1; i <= row_size; ++i) {
        if (!queen_is_in_attack_pos(i, col)) {
            queens_row_num[col] = i;
            go_through_board(col);
            queens_row_num[col] = 0;
        }
    }
}