Sudoku
数独の盤面が与えられたとき、それが有効なものかどうかを判定する問題です。
有効な の数独盤面には、以下の条件がすべて満たされている必要があります:
- 各行に 1 から 9 までの数字がすべて含まれている。
- 各列に 1 から 9 までの数字がすべて含まれている。
- の各ブロックに 1 から 9 までの数字がすべて含まれている。
つまり、無効な数独の盤面には、以下のような問題が発生している可能性があります:
- ある行に同じ数字が重複している。
- ある列に同じ数字が重複している。
- のブロック内で同じ数字が重複している。
Input
入力として、 の数値グリッドが与えられます。埋まっている数字は 0 から 9 の整数で、空欄は 0 で表されます。
Output
もし盤面が有効であればプログラムは
Valid と出力し、それ以外の場合は Not valid と出力してください。Examples
入力 (Input) | 出力 (Output) |
0 0 0 0 0 8 0 0 2
0 7 0 0 0 0 0 1 0
0 2 0 7 0 0 9 0 0
0 0 0 0 0 0 7 0 1
0 0 0 9 0 2 6 0 0
3 0 5 8 0 0 0 4 0
9 0 0 6 0 0 4 0 0
0 0 0 2 0 7 0 6 0
0 0 1 0 0 4 0 0 0 | Valid |
0 0 0 0 0 8 0 0 2
0 7 0 0 0 0 0 1 0
0 2 0 7 0 0 9 0 0
0 0 0 0 0 0 7 0 1
0 6 0 9 0 2 6 0 0
3 0 5 8 0 0 0 4 0
9 0 0 6 0 0 4 0 0
0 0 0 2 0 7 0 6 0
0 0 1 0 0 4 0 0 0 | Not valid |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB