Consider a 9 by 9 grid of squares. It is partitioned into 9 blocks,
each of which is a 3 by 3 grid. Some squares contain a number from
1 to 9, and the rest are blank. Your task is to fill in each blank
with a number (also from 1 to 9) so that
1) no row contains the same number twice, and
2) no column contains the same number twice, and
3) no block contains the same number twice.
You may assume that the problem instances you are given either have
a unique solution or have no solution. If a solution exists, you must
print it out.
Input Format
------------
The file contains multiple problem instances. The first line contains
the number of instances. Each instance consists of 9 lines. Each of
those lines consists of 9 numbers, separated by single spaces.
Output Format
-------------
For each instance, generate one line giving the instance number (see
sample output).
If no solution exists, you must print "No solution." on a separate
line.
If a solution exists, print it using the same format as the input.
Sample Input
------------
2
0 0 0 9 1 0 0 0 6
4 0 6 8 0 5 0 0 0
0 2 0 4 6 0 0 7 0
0 4 1 0 0 0 0 0 0
2 0 5 0 0 0 4 0 3
0 0 0 0 0 0 2 5 0
0 1 0 0 4 8 0 3 0
0 0 0 3 0 1 5 0 7
7 0 0 0 5 6 0 0 0
2 0 0 0 8 5 0 0 0
9 5 0 0 0 6 0 7 0
0 0 0 0 0 0 4 3 0
0 6 0 0 0 0 8 0 0
4 0 0 8 0 1 0 0 2
0 0 9 0 0 0 0 4 0
0 7 6 0 0 0 0 0 0
0 2 0 1 0 0 0 9 7
0 0 0 2 5 0 0 0 0
Sample Output
-------------
Instance 1:
8 5 7 9 1 2 3 4 6
4 3 6 8 7 5 9 1 2
1 2 9 4 6 3 8 7 5
3 4 1 5 2 9 7 6 8
2 6 5 1 8 7 4 9 3
9 7 8 6 3 4 2 5 1
5 1 2 7 4 8 6 3 9
6 8 4 3 9 1 5 2 7
7 9 3 2 5 6 1 8 4
Instance 2:
No solution.
Saturday, June 27, 2009
63. BEFORE "SUDOKU " NAME WAS discovered
Subscribe to:
Post Comments (Atom)
1 comments:
Sol in c++:
#include iostream.h
void prints(int s[9][9]) {
for (int i=0; i<9; i++) {
for (int j=0; j<8; j++)
cout << s[i][j] << " ";
cout << s[i][8] << "\n";
}
}
void fillin(bool a[9][9][10], int s[9][9], int i, int j, int entry) {
// fill in an entry and adjust a to rule out having another of that same
// number in the same row, column or 3x3 box.
s[i][j] = entry;
for (int k=0; k<9; k++) {
a[i][k][entry] = (j==k);
a[k][j][entry] = (i==k);
}
for (int k=i-(i%3); k<(i+3)-(i%3); k++)
for (int l=j-(j%3); l<(j+3)-(j%3); l++)
a[k][l][entry] = (k==i && l==j);
for (int v=1; v<=9; v++)
a[i][j][v] = (v==entry);
}
bool solve(bool a[9][9][10], int s[9][9]) {
bool done = false;
// find a blank with minimum number of possibilities
int m = 10;
int besti, bestj;
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
if (!s[i][j]) { // consider blanks only
int x = 0;
for (int v=1; v<=9; v++)
if (a[i][j][v])
x++;
if (xLTm) {
m = x;
besti = i;
bestj = j;
}
}
}
}
if (m==10) { // no blanks left; print solution and //stop
prints(s);
done = true;
}
else { // try plugging different values into best location
for (int v=1; vLT=9; v++) {
if (!done && a[besti][bestj][v]) {
// make copies, fill in one value and try solving
bool aTry[9][9][10];
int sTry[9][9];
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
sTry[i][j] = s[i][j];
for (int k=1; k<=9; k++)
aTry[i][j][k] = a[i][j][k];
}
}
fillin(aTry,sTry,besti,bestj,v);
done = solve(aTry,sTry);
}
}
}
return done;
}
main() {
int num; // number of instances
cin >> num;
for (int instance = 1; instance <= num; instance++) {
cout << "Instance " << instance << ":\n";
bool a[9][9][10]; // a[i,j,v] stores true if v is a possible
// value for cell i,j
int s[9][9]; // stores the puzzle
for (int i=0; i<9; i++) // start with a all true
for (int j=0; j<9; j++)
for (int v=1; v<=9; v++)
a[i][j][v] = true;
for (int i=0; i<9; i++) // read input (0's indicate blanks) and
// initialize array a
for (int j=0; j<9; j++) {
int entry;
cin >> entry;
if (entry) fillin(a,s,i,j,entry);
else s[i][j]=0;
}
if (!solve(a,s)) cout << "No solution.\n";
}
}
Post a Comment