Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1898
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 subgrids, indicated by the thick lines. To solve the puzzle you have to fill the empty places with digits according to the following 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; • ‘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: 1 5 3 9 8 4 7 6 2 8 4 2 7 3 6 1 5 9 6 9 7 5 1 2 8 3 4 2 3 8 6 7 1 4 9 5 9 7 4 3 2 5 6 1 8 5 1 6 8 4 9 3 2 7 7 6 5 4 9 3 2 8 1 3 8 1 2 5 7 9 4 6 4 2 9 1 6 8 5 7 3 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 0 0 3 9 0 0 7 6 0 0 4 0 0 0 6 0 0 9 6 0 7 0 1 0 0 0 4 2 0 0 6 7 0 0 9 0 0 0 4 3 0 5 6 0 0 0 1 0 0 4 9 0 0 7 7 0 0 0 9 0 2 0 1 3 0 0 2 0 0 0 4 0 0 2 9 0 0 8 5 0 0 0 0 3 9 0 0 7 6 0 0 4 0 0 0 6 0 0 9 6 0 0 0 1 0 0 0 4 0 0 0 6 7 0 0 9 0 0 0 4 0 0 5 6 0 0 0 1 0 0 4 9 0 0 0 7 0 0 0 9 0 2 0 1 3 0 0 2 0 0 0 4 0 0 2 0 0 0 8 5 0 0 0 0 3 9 0 0 7 6 0 0 4 0 0 0 6 0 0 9 6 0 7 0 1 0 0 0 4 2 0 0 6 7 0 0 9 0 0 0 4 3 0 5 6 0 0 0 1 0 0 4 9 0 0 7 7 2 0 0 9 0 2 0 1 3 0 0 2 0 0 0 4 0 0 2 9 0 0 8 5 0 0 0 0 3 9 0 0 7 6 0 0 4 0 0 0 6 0 0 9 6 0 7 0 1 0 0 0 4 2 0 0 6 7 0 0 9 0 0 0 4 3 0 5 6 0 0 0 1 0 0 4 9 0 0 7 7 5 0 0 9 0 2 0 1 3 0 0 2 0 0 0 4 0 0 2 9 0 0 8 5 0 0
Sample Output Case 1: Unique. Case 2: Ambiguous. Case 3: Illegal. Case 4: Impossibl
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
const int n=9,n1=3;
vector<int> row,col,sq;
vector < vector<int>> board;
int solve(int x,int y){
if(x==n) return 1;
else if(y==n) return solve(x+1,0);
if(board[x][y] != 0) return solve(x,y+1);
int sqIdx = (x/n1)*n1+y/n1;
int validBit = row[x] & col[y] & sq[sqIdx];
int solCnt = 0;
while(validBit != 0){
int p = validBit & -validBit;
row[x] ^= p;
col[y] ^= p;
sq[sqIdx] ^= p;
solCnt += solve(x,y+1);
if(solCnt > 1) return 2;
row[x] ^= p;
col[y] ^= p;
sq[sqIdx] ^= p;
validBit -= p;
}
return solCnt;
}
int main() {
int tc=1,v;
while(scanf("%d",&v) != EOF) {
row.assign(n,(1<<n) - 1);
col.assign(n,(1<<n) - 1);
sq.assign(n,(1<<n) - 1);
board.clear();
bool alreadyInvalid = false;
for(int i=0;i<n;i++){
vector<int> r;
for(int j=0;j < n;j++){
if(i+j != 0)scanf("%d",&v);
r.push_back(v);
if(v != 0) {
v--;
int sqIdx = (i/n1)*n1+j/n1;
if(((row[i]>>v)&1) == 0) alreadyInvalid = true;
if(((col[j]>>v)&1) == 0) alreadyInvalid = true;
if(((sq[sqIdx]>>v)&1) == 0) alreadyInvalid = true;
row[i] ^= (1<<v);
col[j] ^= (1<<v);
sq[sqIdx] ^= (1<<v);
}
}
board.push_back(r);
}
printf("Case %d: ",tc++);
if(alreadyInvalid) printf("Illegal.\n");
else {
int sol = solve(0,0);
if(sol == 0) printf("Impossible.\n");
else if(sol == 1) printf("Unique.\n");
else printf("Ambiguous.\n">;
}
}
}
Input
0 4 0 0 0 6 0 0 9
6 0 7 0 1 0 0 0 4
2 0 0 6 7 0 0 9 0
0 0 4 3 0 5 6 0 0
0 1 0 0 4 9 0 0 7
7 0 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 9 0 0 8 5 0 0
0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 0 0 1 0 0 0 4
0 0 0 6 7 0 0 9 0
0 0 4 0 0 5 6 0 0
0 1 0 0 4 9 0 0 0
7 0 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 0 0 0 8 5 0 0
0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 7 0 1 0 0 0 4
2 0 0 6 7 0 0 9 0
0 0 4 3 0 5 6 0 0
0 1 0 0 4 9 0 0 7
7 2 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 9 0 0 8 5 0 0
0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 7 0 1 0 0 0 4
2 0 0 6 7 0 0 9 0
0 0 4 3 0 5 6 0 0
0 1 0 0 4 9 0 0 7
7 5 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 9 0 0 8 5 0 0
Output
Case 2: Ambiguous.
Case 3: Illegal.
Case 4: Impossible.
Demonstration
UVA Online Judge solution - 10957-So Doku Checker - UVA Online Judge solution in C,C++,java