POJ 2918 - Tsudoku

http://poj.org/problem?id=2918

概要

簡単に機械的に解くことができる数独のサブセット Tsudoku を解く．

Tsudoku は，いずれかの行，列，3 x 3 のブロックがちょうど8個の数字で埋まっていたら，最後の一つを残りの数字で埋める，という手順を繰り返すと解くことができる．

制約

特になし

解法

やるだけ．

数字が埋められていない場所を覚えて，それが空になるまで手順を繰り返すという方法で実装した．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int T;
 8   cin >> T;
 9   for (int Ti = 1; Ti <= T; Ti++) {
10     char grid[9][10];
11     vector<pair<int,int> > zeros;
12     for (int i = 0; i < 9; i++) {
13       cin >> grid[i];
14       for (int j = 0; j < 9; j++) {
15         if (grid[i][j] == '0') {
16           zeros.push_back(make_pair(i, j));
17         }
18       }
19     }
20 
21     while (!zeros.empty()) {
22       for (vector<pair<int,int> >::iterator it = zeros.begin(); it != zeros.end();) {
23         const int i = it->first, j = it->second;
24         int s = 45;
25         int c = 0;
26         for (int k = 0; k < 9; k++) {
27           if (grid[k][j] == '0') {
28             ++c;
29           } else {
30             s -= grid[k][j]-'0';
31           }
32         }
33         if (c == 1) {
34           grid[i][j] = '0'+s;
35           it = zeros.erase(it);
36           goto NEXT;
37         }
38 
39         s = 45; c = 0;
40         for (int l = 0; l < 9; l++) {
41           if (grid[i][l] == '0') {
42             ++c;
43           } else {
44             s -= grid[i][l]-'0';
45           }
46         }
47         if (c == 1) {
48           grid[i][j] = '0'+s;
49           it = zeros.erase(it);
50           goto NEXT;
51         }
52 
53         s = 45; c = 0;
54         for (int k = 0; k < 3; k++) {
55           for (int l = 0; l < 3; l++) {
56             if (grid[i-i%3+k][j-j%3+l] == '0') {
57               ++c;
58             } else {
59               s -= grid[i-i%3+k][j-j%3+l]-'0';
60             }
61           }
62         }
63         if (c == 1) {
64           grid[i][j] = '0'+s;
65           it = zeros.erase(it);
66           goto NEXT;
67         }
68         ++it;
69 NEXT:
70         ;
71       }
72     }
73 
74     cout << "Scenario #" << Ti << ":" << endl;
75     for (int i = 0; i < 9; i++) {
76       cout << grid[i] << endl;
77     }
78     cout << endl;
79   }
80   return 0;
81 }