The best logical puzzles often are puzzles that are based on a simple idea. So Doku is one such type of puzzle. Although So Dokus have been around for some twenty years, in the last few years they conquered the world exponentially. Hundreds of newspapers and websites are now publishing them on a daily basis. For those of you unfamiliar with these puzzles, let me give a brief introduction. The picture above contains an example of a Su Doku puzzle. As you can see, we have a 9 × 9 grid filled with single digits from 1 to 9 and empty places. The grid is further divided into nine 3 × 3 sub-grids, indicated by the thick lines. To solve the puzzle you have to fill the empty places with digits according to the fol- lowing rules: • Every row should contain the digits 1 to 9 exactly once; • Every column should contain the digits 1 to 9 exactly once; • Every 3 × 3 sub-grid should contain the digits 1 to 9 exactly once. A well formed Su Doku can be solved with paper and pencil using logical deduction only. To be well formed it should be legal (no row, column or sub-grid contains a digit more than once), solvable (the empty places can all be filled while respecting the rules) and unique (there is only one solution). This is what your program is going to check. Input The input contains several (partially) filled grids, each representing a Su Doku puzzle. For every puzzle there are 9 lines with 9 digits giving the puzzle in row major order. Empty places in the puzzle are represented by the digit ‘0’ (zero). Digits on a line are separated by one space. The grids are separated by one empty line. The first grid in the sample input represents the puzzle given in the picture. Output For every grid in the input, determine one of the following four verdicts: • ‘Illegal’ if the puzzle violates one of the three rules; • ‘Unique’ if only one solution exists; • ‘Ambiguous’ if more than one solution exists;
2/3 • ‘Impossible’ if no solution exists; Print one line per grid, in the format: ‘Case < N >: < V ERDICT >.’, where N is the case number, starting from 1, and V ERDICT is one of the four words in the list. See the sample output for the exact format. Note: an ‘Illegal’ puzzle is also ‘Impossible’, of course, but your program should print ‘Illegal’ in that case. Only print ‘Impossible’ if the input doesn’t violate one of the three rules, but the puzzle still can’t be solved. EPILOGUE (not required to solve the problem) The (unique) solution to the given puzzle is: 153984762 842736159 697512834 238671495 974325618 516849327 765493281 381257946 429168573 If you are interested in the fascinating world of Su Dokus and solving them by hand, Google is a good starting point. Also Wikipedia has a nice entry on Su Dokus describing their history and giving some mathematical background. Sample Input 003900760 040006009 607010004 200670090 004305600 010049007 700090201 300200040 029008500 003900760 040006009 600010004 000670090 004005600 010049000 700090201 300200040 020008500 003900760 040006009 607010004
3/3 200670090 004305600 010049007 720090201 300200040 029008500 003900760 040006009 607010004 200670090 004305600 010049007 750090201 300200040 029008500 Sample Output Case 1: Unique. Case 2: Ambiguous. Case 3: Illegal. Case 4: Impossible.