2
\$\begingroup\$

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 help me to point out any bad habits, better algorithms or better c++ paradigms

Thanks in advance!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Heslacher Sep 25 '18 at 5:30
2
\$\begingroup\$
  • 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ The if/else should rather read if (!check) return false;. Early return and decreased nesting are always preferable \$\endgroup\$ – miscco Sep 24 '18 at 17:57
  • \$\begingroup\$ @miscco Agreed. \$\endgroup\$ – vnp Sep 24 '18 at 17:59
  • \$\begingroup\$ 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. \$\endgroup\$ – Kian Lee Sep 24 '18 at 23:06
  • \$\begingroup\$ @miscco Good to know eary return idiom, thanks! \$\endgroup\$ – Kian Lee Sep 24 '18 at 23:10
  • \$\begingroup\$ @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. \$\endgroup\$ – vnp Sep 24 '18 at 23:14
2
\$\begingroup\$

@vnp already made a good comment about refactoring the check into its of function, I would like to add a bit about other aspects:

  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

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Kian Lee Sep 24 '18 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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