# Codeforces: Queens, Again

code review friends/teachers! This is a trivial(no dfs/permutations/backtrace required) n queen problem from codeforces: B. 8 Queens, Again!!

### input

2

A1 B5 C8 D6 E3 F7 G2 H4

C3 E4 C4 E1 C4 F4 A8 G6

### output

Valid

Invalid

Here is my solution:

### queen.h

#ifndef QUEEN
#define QUEEN
#include <array>
constexpr int N = 8;

void paint(std::array<std::array<int, N>, N>& m, int x, int y);

bool check(const std::array<std::array<int, N>, N>& m, int x, int y);

#endif


### queen.cpp

#include "queen.h"

#include <cstdlib>
#include <iostream>
#include <string>

void paint(std::array<std::array<int, N>, N>& m, int x, int y)
{
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
if(i == x || j == y || abs(i - x) == abs(j - y))
{
m[i][j] = 1;
}
}
}
}

bool check(const std::array<std::array<int, N>, N>& m, int x, int y)
{
if(m[x][y] == 1)
{
return false;
}
return true;
}


### testqueen.h

#define CATCH_CONFIG_MAIN // This tells Catch to provide a main() - only do this
// in one cpp file
#include "catch.hpp"
#include "queen.h"

#include <iostream>
#include <sstream>

TEST_CASE("eight queens test")
{
std::ostringstream out;
std::streambuf* coutbuf = std::cout.rdbuf();

std::cout.rdbuf(out.rdbuf()); // redirect cout to out
int n;
std::cin >> n;

for(int i = 0; i < n; i++)
{
std::array<std::array<int, 8>, 8> arr{};
std::string s;
for(int j = 0; j < N; j++)
{
std::cin >> s;
auto x = s[0] - 'A', y = s[1] - '1';
if(check(arr, x, y) == true)
{
paint(arr, x, y);
}
else
{
std::cout << "Invalid" << '\n';
for(int k = j + 1; k < N; k++)
{
std::cin >> s;
}
break;
}
if(j == N - 1)
{
std::cout << "Valid" << '\n';
}
}
}
std::cout.rdbuf(coutbuf);
REQUIRE(out.str() == "Valid\nInvalid\n");
}


### Test:

~/.../codeforces/100947-B(eight-queen) >>> ./build/test/tests                       ±[●●][master]
2
A1 B5 C8 D6 E3 F7 G2 H4
C3 E4 C4 E1 C4 F4 A8 G6
===========================================================
All tests passed (1 assertion in 1 test case)


• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Sep 25, 2018 at 5:30

• check features a well-known anti-idiom:

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


is a long way to say

return !condition;

• Testing for j == N - 1 in a loop looks unappealing. The code would be much cleaner if the inner loop (which actually decides on the problem) were factored out into a function:

bool is_position_valid(....)
{
....
for (int j = 0; j < N; j++) {
if (check(....)) {
paint(....);
} else {
return false;
}
}
return true;
}


and the caller produced the required output.

• The complexity is quadratic in both time and space. There is a way to drive the down to linear: have 4 arrays of sizes N, N, 2*N - 1, 2*N - 1 (for files, ranks, and left and right diagonals respectively), and for each queen mark a corresponding entry as taken; if the entry is already taken the position is invalid.

• The if/else should rather read if (!check) return false;. Early return and decreased nesting are always preferable Sep 24, 2018 at 17:57
• @miscco Agreed.
– vnp
Sep 24, 2018 at 17:59
• Thanks, vnp! I'm still a little confused about your linear solution: if ranks means matrix-rank, how to make use of it for the queen? why left and right diagonals need 2*N-1 length. From the two-dimension matrix, each diagonal's size is N, I really don't understand the meaning of 2*N-1. Sep 24, 2018 at 23:06
• @miscco Good to know eary return idiom, thanks! Sep 24, 2018 at 23:10
• @KianLee ranks and files is a chessplayer's lingo for chessboard coordinates. Files go from A to H, and ranks from 1 to 8. The diagonals are A1-A1, B1-A2, ..., H1-A8, H2-B8, ..., H7-G8, H8-H8, (2*8 - 1 = 15 of them), and similarly 15 diagonals going other direction.
– vnp
Sep 24, 2018 at 23:14

1. Naming:

Your variable n counts the number of tests. So you should name it accordingly.

int numTests;
std::cin >> numTests;

for (int test = 0; test  < numTests; ++test ) {


Note that i also changed the loop variable to test and also the post-increment to pre-increment. For basic types such as ints there is no real difference, however oce you start using iterators, post-increment always includes a copy which adds unnecessary overhead.

2. Maybe i am missing it but i dont see the variable N declared.

3. You are already using standard container, which is great, so you should also try to use iterators and more importantly range based loops. In this (arbitraryily simple) program they are not really applicable as you always need the running variable

• Thanks for your awesome comments! I do declare N the fourth line of queue.h. As for post/preincrement iterator, I think, for a decent modern compiler, nothing different.. godbolt.org/z/UI2ygL VS gcc.godbolt.org/z/IH_vw3 Sep 24, 2018 at 22:48