Problem 5: No-Horse Sudoku

"No-horse sudoku", as interesting as its name sounds (especially in Chinese), is a kind of irregular sudoku with new rules. In this problem, your goal is to judge whether a given board of "no-horse sudoku" is valid.

Rules

A regular sudoku has 3 rules:

• Every number should appear exactly once in a column.
• Every number should appear exactly once in a row.
• Every number should appear exactly once in a "palace" (any of the nine equally divided $3\times3$ regions).

For "no-horse sudoku", we have an additional rule related to a concept "horse step".

Similar to the rules of horses in chess, we define that two grids share a "horse step" if they lie diagonally in a $2 \times 3$ or $3 \times 2$ rectangle (The pair (E5, C4), for example).

Now here comes the additional rule:

• Any two grids sharing a "horse step" should not be filled in with the same number.

Your Task

Write a program that reads in an entire sudoku board and judges whether the board is valid under the "no-horse sudoku" rules. The whole board is valid if and only if all the numbers in the grids are valid.

It is recommended that you implement such a function (or anything similar to this), which can help you make your code clear and readable.

bool checkOneNumber(int (*board)[9], int row, int col);

• Brief: Judges whether the number in the grid board[row][col] is valid under the "no-horse sudoku" rules.
• Parameters:
  • board: a $9\times 9$ array representing the sudoku board
  • row: the row index of the target grid
  • col: the column index of the target grid
• Return value: true if the number in that grid is valid, false otherwise.

Input:

$9$ lines, each line containing $9$ numbers separated by space, representing a row of the sudoku board. The $i$-th line of the input represents the $i$-th row (top to bottom) in the sudoku board.

Output:

1 or 0. Output 1 if the board is valid, and 0 otherwise.

Important Note

We will check whether you earned your score for this problem in a proper way. Some tricks may get you a high score on OJ, but it will be in vain in the end.

Samples

Some examples of valid boards:

8 6 4 3 1 5 2 9 7
5 1 7 9 6 2 3 8 4
3 2 9 7 8 4 1 5 6
4 3 6 8 7 1 9 2 5
1 7 5 2 3 9 6 4 8
9 8 2 5 4 6 7 1 3
6 9 1 4 5 7 8 3 2
7 5 3 1 2 8 4 6 9
2 4 8 6 9 3 5 7 1

1 4 3 7 8 9 6 2 5
2 5 9 3 4 6 1 8 7
6 7 8 2 5 1 3 9 4
9 6 4 8 7 5 2 3 1
5 3 1 9 6 2 4 7 8
8 2 7 1 3 4 9 5 6
4 9 2 5 1 7 8 6 3
3 1 5 6 9 8 7 4 2
7 8 6 4 2 3 5 1 9

Some examples of boards that are valid under normal rules but invalid with the "no-horse" rule:

6 8 4 5 1 7 3 9 2
7 2 9 3 4 8 5 6 1
1 3 5 2 6 9 4 8 7
5 1 6 8 3 2 9 7 4
8 9 7 1 5 4 2 3 6
2 4 3 9 7 6 8 1 5
3 7 1 4 9 5 6 2 8
9 5 2 6 8 1 7 4 3
4 6 8 7 2 3 1 5 9

5 3 2 8 7 1 4 6 9 
4 9 6 2 5 3 1 8 7 
8 7 1 9 4 6 5 2 3 
3 5 7 1 6 4 8 9 2 
9 6 4 3 8 2 7 5 1 
1 2 8 5 9 7 6 3 4 
7 8 5 4 2 9 3 1 6 
6 1 9 7 3 5 2 4 8 
2 4 3 6 1 8 9 7 5