Check Sudoku

See the original problem on HackerRank.

Solutions

We need to check if any row, columns or sub-grid contains duplicates. We can use an array of booleans (or a frequency array) for each type of component to check.

Here is the idea:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int main() 
{
    bool row[9][9]{}, column[9][9]{}, grid[3][3][9]{};
    int N, r, c, v;
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
      cin >> r >> c >> v;
      r--; c--; v--;
      if (row[r][v] || column[c][v] || grid[r / 3][c / 3][v]) 
      {
        cout << "WRONG INPUT";
        return 0;
      }
      row[r][v] = column[c][v] = grid[r / 3][c / 3][v] = true;
    }
    cout << "OK";
}

Basically, we read a coordinate and we check if it has been already allocated in any of the component.

This problem can be used to think about the design. For example:

• what if multiple occurrences are allowed? (maybe boolean arrays will be replaced with frequency tables)
• what if the grid dimensions are not statically known?
• what if the grid shape is different (N-dimensional)?
• what if the check requirements can change dynamically?