Not an official ACM page
[ Problem E | 1992 ACM East-Central Regional problem set | My ACM problem archive | my home page]
1992 ACM East Central Regional Programming Contest


Hip to be Square

Writings discovered inside the walls of the Great Pyramids have often revealed the ancient Egyptian's affinity for mathematical logic and problem solving.

Recently, a team of archaeologists returning from an expedition to the pyramids brought back several examples of ancient hieroglyphics which, when translated into their English equivalents, provided further evidence of their mathematical prowess.

The grid at the left, one of many derived from the hieroglyphics, was presented to a team of mathematical scholars for their analysis. After careful study, they determined that this grid represented a mathematical challenge. To the best of their knowledge, the goal seems to be to fill in the empty spaces with the numbers from one through nine, subject to the following constraints:

In an effort to better understand this ancient civilization (and to use the technology of the present to address the challenges of the past), your team has decided to develop a program that will "complete the squares", so to speak, found in the pyramids.

Input

The input will consist of a series of Egyptian squares. On the first line of the input file will be a single integer stating the number of Egyptian squares in the dataset. This will be followed by data for that many Egyptian squares. Each Egyptian square will consist of nine lines of nine single-digit integers that are separated by spaces. In each Egyptian square, at least four fixed numbers in each row, column, and smaller square of nine will be provided, with the empty spaces denoted by the integer zero. Every number from 1 to 9 will appear at least once in each Egyptian square as a fixed digit. Only valid data will appear in the input file.

Output

Since the Egyptians prided themselves on their mathematical abilities, it is safe to assume that each square will have at least one solution. Should multiple answers be possible, your program may output any of these answers (but only one). Each Egyptian square is to be assigned an identification number, beginning with square #1. A heading of EGYPTIAN SQUARE #n should be output, followed by a blank line, and the lines showing the solved square. The numbers within an Egyptian square should be output right-justified in a field width of two character positions. The output for one Egyptian square is to be separated from the output of the next Egyptian square by a blank line. Refer to the example on the next page.

Sample Input

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

Output for the Sample Input

EGYPTIAN SQUARE #1

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

EGYPTIAN SQUARE #2

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

This page maintained by Ed Karrels.
Last updated December 12, 1999