POJ 2676 Sudoku
http://poj.org/problem?id=2676挺有意思的题目
题意：九宫格数独，给出题目，打出数独的答案
思路：dfs，三种约束条件做为剪枝
http://poj.org/images/2676_1.jpg
#include <iostream>#include <iomanip>#include <fstream>#include <sstream>#include <algorithm>#include <string>#include <set>#include <Map>#include <utility>#include <queue>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <ctype.h>using namespace std;char Map;bool row, col, cube, flag; //存在性表int find (int x) //寻找所在九宫格的坐标{if (x < 3)return 0;if (x < 6)return 1;return 2;}void dfs (int times) //times是扫描次数{if (flag)return ;if (times >= 81) //扫描完全部，就代表填完数了{flag = true;return ;}int h, k, x, y, i;h = times / 9;k = times % 9; //求出扫描第times次时的格子坐标if (Map != '0'){dfs (times+1); //已经有数，扫描下一个return ;}x = find(h);y = find(k);for (i = 1; i <= 9; i++){if (!row && !col && !cube){ //第h行是否存在i，第k列是否存在i，第（x，y）个九宫格是否存在irow = col = cube = true;Map = i + '0';/*printf ("0-----\n"); //打表调试for (int j = 0; j < 9; j++)cout << Map << endl;printf ("\n");*/dfs (times+1);if (flag)return ;row = col = cube = false;Map = '0'; //回溯}}return ;}int main(){int i, j, x, y, t;cin >> t;getchar();while (t--){memset (row, false, sizeof(row));memset (col, false, sizeof(col));memset (cube, false, sizeof(cube));for (i = 0; i < 9; i++){for (j = 0; j < 9; j++){scanf ("%c", &Map);if (Map != '0'){row-'0'] = true;col-'0'] = true;x = find(i);y = find(j);cube-'0'] = true;}}getchar();}flag = false;dfs (0);for (i = 0; i < 9; i++)printf ("%s\n", Map);}return 0;}
页:
[1]