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 boardrow
: the row index of the target gridcol
: 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