Codeforces: Queens, Again

Question

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!

Answer 1

• 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.

Answer 2

@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