Find the next empty column on a chessboard [closed]

Question

I was playing around with the "eight queens" problem, just to see how I could use C++ algorithms to write less code.

I figured out a way to find the next unused column using find_if_not. I am showing both ways of writing it. Assume we are looping over every valid "file" on a given "rank" ( in C++ terms, I am looping over rows and columns in an 8x8 matrix.)

• used is simply a set of column indexes that are currently occupied by a queen.
• col is the current index of the column where we will try to place the next queen.

Note for efficiency, the array of column indexes would not be created where it's shown in the code.

Method1:

set<unsigned>::iterator it;
for (; col < 8; ++col)
{
    it = used.find(col);
    if (it == used.end())
        break;
}
if (it != used.end())
    return false;

Method2:

array<unsigned, 8> colIdx{ 0, 1, 2, 3, 4, 5, 6, 7 };
auto it = find_if_not(colIdx.begin() + col, colIdx.end(),
    [&used](unsigned colIdx) { return used.find(colIdx) != used.end(); });
if (it == colIdx.end())
    return false;
else
    col = *it;

Answer 1

Manually listing the numbers from 0 to 7 is a bad sign; I would definitely consider your first method more readable.

Have you considered using an array(-like) of booleans instead of a set, though?

// given array<bool, 8> used;
auto const it = std::find(used.cbegin() + col, used.cend(), false);

if (it == used.cend())
    return false;

col = std::distance(used.cbegin(), it);

It should be faster, too, with no downside that I can think of (since your set and array capacity will be the same).

Then there’s the possibility that the overall code can be structured so you only need an iterator and never an index (except to produce results)…

Alternatively, it still makes the first method simpler.

for (; col < 8; ++col)
    if (!used[col])
        break;

if (col == 8)
    return false;

or

while (used[col])
    if (++col == 8)
        return false;

Answer 2

I prefer Method 2 because the loop is replaced by a standard algorithm, which has a fixed meaning and is hence widely known.

As far as hardcoding the colIdx array is concerned, you can use std::iota() to generate the numbers instead.

Also, you use magic number for loop counter in Method 1, it should be replaced with used.size().