1162. SudokuConstraints
Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge
Description
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3×3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3×3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.
Input
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
Output
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.
Sample Input1103000509002109400000704000300502006060000050700803004000401000009205800804000107Sample Output143628579572139468986754231391542786468917352725863914237481695619275843854396127
#include <iostream>#include <vector>#include <string.h>#include <cstring>#include <stdio.h>#include <algorithm>using namespace std;//数独题，深搜，这是剪枝的char ans[10][10];//用来储存最终答案bool num_in_row[10][10], num_in_col[10][10], num_in_blo[10][10];//这里的数组[i][j]表示在第i行/列/块里面已经有了j这个数字（有的时候为true）bool is_ok;//是否找到了答案int blank_num;//空白的数目struct Blank {int pos_row, pos_col, pos_blo, possibility;//其中的possibility就是表示可能的数字的个数}blank[85];int find_block(int x, int y) {//返回属于的块编号int block[10][10] ={0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 1, 1, 1, 2, 2, 2, 3, 3, 3,0, 1, 1, 1, 2, 2, 2, 3, 3, 3,0, 1, 1, 1, 2, 2, 2, 3, 3, 3,0, 4, 4, 4, 5, 5, 5, 6, 6, 6,0, 4, 4, 4, 5, 5, 5, 6, 6, 6,0, 4, 4, 4, 5, 5, 5, 6, 6, 6,0, 7, 7, 7, 8, 8, 8, 9, 9, 9,0, 7, 7, 7, 8, 8, 8, 9, 9, 9,0, 7, 7, 7, 8, 8, 8, 9, 9, 9};return block[x][y];}void dfs(int blank_now) {//blank_now指当前要填的空的编号if (is_ok == true)//找到答案了就返回return;if (blank_now == blank_num) {//如果blank_now超过了总的空白数，也就是说空白都填完了那就返回is_ok = true;return;}for (int possible = 1; possible <= 9; possible++) {//在一个空上有9种可能if (!num_in_row[blank[blank_now].pos_row][possible] && !num_in_col[blank[blank_now].pos_col][possible] && !num_in_blo[blank[blank_now].pos_blo][possible]) {ans[blank[blank_now].pos_row][blank[blank_now].pos_col] = possible + '0';//先填入答案中，就算不对，，后来填的也可以覆盖num_in_row[blank[blank_now].pos_row][possible] = true;//并更新这个空白的限制信息num_in_col[blank[blank_now].pos_col][possible] = true;num_in_blo[blank[blank_now].pos_blo][possible] = true;dfs(blank_now + 1);//深搜if (is_ok)//找到答案直接返回完事return;num_in_row[blank[blank_now].pos_row][possible] = false;//程序运行到这说明前面的假设没找到答案，因此还原这个空白的限制信息num_in_col[blank[blank_now].pos_col][possible] = false;num_in_blo[blank[blank_now].pos_blo][possible] = false;}}}void set_blank(int k, int i, int j) {blank[k].possibility = 0;blank[k].pos_row = i;blank[k].pos_col = j;blank[k].pos_blo = find_block(i, j);}void calculate(int k) {//这里是计算可能的数的个数for (int temp = 1; temp <= 9; temp++) {if (!num_in_row[blank[k].pos_row][temp] && !num_in_col[blank[k].pos_col][temp] && !num_in_blo[blank[k].pos_blo][temp]) {blank[k].possibility++;}}}bool cmp(const Blank &a, const Blank &b) {//按照从小到大的顺序排序return a.possibility < b.possibility;}int main() {int case_num, i, j;scanf("%d", &case_num);while (case_num–) {blank_num = 0;is_ok = false;memset(num_in_row, false, sizeof(num_in_row));memset(num_in_col, false, sizeof(num_in_col));memset(num_in_blo, false, sizeof(num_in_blo));for (i = 1; i <= 9; i++) {scanf("%s", ans[i] + 1);}for (i = 1; i <= 9; i++) {for (j = 1; j <= 9; j++) {if (ans[i][j] != '0') {//不是空白就更新限制信息num_in_row[i][ans[i][j] – '0'] = true;//更新限制信息num_in_col[j][ans[i][j] – '0'] = true;num_in_blo[find_block(i, j)][ans[i][j] – '0'] = true;} else {set_blank(blank_num, i, j);blank_num++;}}}for (i = 0; i < blank_num; i++) {//计算possibilitycalculate(i);}sort(blank, blank + blank_num, cmp);//排序，也就是剪枝dfs(0);for (i = 1; i <= 9; i++) {for (j = 1; j <= 9; j++) {printf("%c", ans[i][j]);}printf("\n");}}return 0;}
原来和文字沾上边的孩子从来都是不快乐的，
