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!

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

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.

• miscco: The if/else should rather read if (!check) return false;. Early return and decreased nesting are always preferable
• vnp: @miscco Agreed.
• Kian Lee: 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.
• vnp: @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.
• Kian Lee: I have implemented the linear solutions, thanks again!

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

• Kian Lee: 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