1132 . Sudoku Extension
Description
Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9x9 grid so that each column, each row, and each of the nine 3x3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid.[from wikipedia]
Left figure is the puzzle and right figure is one solution for that puzzle.
It's a very common game for magzine and newspapers, and people like it for killing time. How about adding some features to this game, some cells can only be filled with even number, some cells can only be filled with odd number, and some cells can only be filled with the same number. Great, let's call it "Sudoku Extention".
It's very easy to give one possible solution a Sudoku Extension puzzle, but do you know how many solutions are there for a certain Sudoku Extension problem? Let's find out!
Input Format
The input data will start with the number of test cases. For each test case, 9 lines followed, corresponding to the rows of the table. On each line, a string of exactly 9 characters is given, it's either 0-9 digit, or a-z alpha in lower case. '1' - '9' means the cell is already filled in; '0' means this cell is empty; 'e' means the cell need to be filled with a even number; 'o' means the cell need to be filled with an odd number; other alpha of 'a' - 'z', except 'e' and 'o' denote a variable, so if two or more cells denoted by 'a', then they must be filled with the same number.
Output Format
The output for each case is the number of possible solutions, note for each case, the solution will be less than 3000, and there's not more than 10 test cases.
Sample Input 1
1 040008007 00e030408 006000200 301004000 0080000o2 000003000 200401005 600070000 800006003
Sample Output 1
507
Hints
Problem Source
Migrated from old NTUJ.
2009Harbin
Subtasks
| No. | Testdata Range | Score |
|---|