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 &lt;array&gt;
constexpr int N = 8;

void paint(std::array&lt;std::array&lt;int, N&gt;, N&gt;&amp; m, int x, int y);

bool check(const std::array&lt;std::array&lt;int, N&gt;, N&gt;&amp; m, int x, int y);

#endif

queen.cpp
#include &quot;queen.h&quot;

#include &lt;cstdlib&gt;
#include &lt;iostream&gt;
#include &lt;string&gt;

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

bool check(const std::array&lt;std::array&lt;int, N&gt;, N&gt;&amp; 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 &quot;catch.hpp&quot;
#include &quot;queen.h&quot;

#include &lt;iostream&gt;
#include &lt;sstream&gt;

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

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

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

Test:
~/.../codeforces/100947-B(eight-queen) &gt;&gt;&gt; ./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 help me to point out any bad habits, better algorithms or better c++ paradigms
Thanks in advance!
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 &lt; 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.