COP 3503 Homework #5

Assigned: 7/22/10 (Thursday)

Due: 8/3/10 (Tuesday 11:55pm WebCourses time, NO LATE ASSIGNMENTS)

Sudoku Puzzles (Call your program sudoku.java)

Sudoku Puzzles have recently caught on as a hot new item amongst games in newspapers. The game is as follows:

1) You are given a 9x9 grid, with some squares filled in with positive integers in between 1 and 9, inclusive.

2) Your goal is to complete the grid with positive integers in between 1 and 9, inclusive, so that each row, column and mini 3x3 square that is designated contain each integer in the range 1 through 9 exactly once.

Below is an example of a Sudoku puzzle.

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

(taken from www.sudoku.com on 11:45am on 2/1/06)

Here is the puzzle solved:

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


Your program will read in a file of sudoku puzzles, all of which either have no solution or a unique solution. You will output to the screen for each test case, either the filled in game board, or the statement, "No solution possible."

Input File Format

The first line of the input file will be a positive integer n, representing the number of puzzles to solve in the input file. The following 9n lines will contain the n cases, with each case taking exactly 9 lines. Within each test case, the ith line will contain the 9 values on the ith row of the unsolved puzzle, in order, from left to right. In particular, all blank entries of the puzzle will be indicated with a 0, and the 9 integer values (all in between 0 and 9, inclusive) on the line each will be separated by a space.

Output Format

The first line for each test case will be of the format:

Test case k:

where k ranges in between 1 and n, inclusive and represents the test case number.

If the puzzle has no solution, then the second line of output will be:

No solution possible.

If the puzzle has a solution, output it on the following 9 lines, with each value separated by one space. Put a blank line between cases. For the puzzle above the output would be:

9 6 3 1 7 4 2 5 8

1 7 8 3 2 5 6 4 9

2 5 4 6 8 9 7 3 1

8 2 1 4 3 7 5 9 6

4 9 6 8 5 2 3 1 7

7 3 5 9 6 1 8 2 4

5 8 9 7 1 3 4 6 2

3 1 7 2 4 6 9 8 5

6 4 2 5 9 8 1 7 3

Sample Input File

1

0 6 0 1 0 4 0 5 0

0 0 8 3 0 5 6 0 0

2 0 0 0 0 0 0 0 1

8 0 0 4 0 7 0 0 6

0 0 6 0 0 0 3 0 0

7 0 0 9 0 1 0 0 4

5 0 0 0 0 0 0 0 2

0 0 7 2 0 6 9 0 0

0 4 0 5 0 8 0 7 0