首页 > 代码库 > POJ3074----Sudoku
POJ3074----Sudoku
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 8575 | Accepted: 3074 |
Description
In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,
. | 2 | 7 | 3 | 8 | . | . | 1 | . |
. | 1 | . | . | . | 6 | 7 | 3 | 5 |
. | . | . | . | . | . | . | 2 | 9 |
3 | . | 5 | 6 | 9 | 2 | . | 8 | . |
. | . | . | . | . | . | . | . | . |
. | 6 | . | 1 | 7 | 4 | 5 | . | 3 |
6 | 4 | . | . | . | . | . | . | . |
9 | 5 | 1 | 8 | . | . | . | 7 | . |
. | 8 | . | . | 6 | 5 | 3 | 4 | . |
Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.
Input
The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.
Output
For each test case, print a line representing the completed Sudoku puzzle.
Sample Input
.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534. ......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3. end
Sample Output
527389416819426735436751829375692184194538267268174593643217958951843672782965341 416837529982465371735129468571298643293746185864351297647913852359682714128574936
Source
把数独问题转成精确覆盖,课设要做这个就来学了下dlx
/************************************************************************* > File Name: sudoku.cpp > Author: ALex > Mail: 405045132@qq.com > Created Time: 2015年01月06日 星期二 14时46分52秒 ************************************************************************/ #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int n = 350; const int m = 800; const int inf = 0x3f3f3f3f; const int N = 1000 * 1000; bool mat[1000][1000]; char su[100]; int cnt[m]; int most; bool ans[N]; int head; struct Node { int up, down, left, right; int col, row; }node[N]; void init (int m) { memset (ans, 0, sizeof(ans)); for (int i = 0; i <= m; ++i) { node[i].left = i - 1; node[i].right = i + 1; node[i].col = i; node[i].up = i; node[i].down = i; cnt[i] = 0; } node[0].left = m; node[m].right = 0; } void remove(int c) { node[node[c].left].right = node[c].right; node[node[c].right].left = node[c].left; for (int i = node[c].down; i != c; i = node[i].down) { for (int j = node[i].right; j != i; j = node[j].right) { --cnt[node[j].col]; node[node[j].up].down = node[j].down; node[node[j].down].up = node[j].up; } } } void resume(int c) { node[node[c].left].right = c; node[node[c].right].left = c; for (int i = node[c].up; i != c; i = node[i].up) { for (int j = node[i].left; j != i; j = node[j].left) { ++cnt[node[j].col]; node[node[j].down].up = j; node[node[j].up].down = j; } } } bool Dacing_Link_X() { if (node[324].right == 324) { return true; } int mins = inf; int c; for (int i = node[324].right; i != 324; i = node[i].right) { if (cnt[i] < mins) { mins = cnt[i]; c = i; } } remove(c); for (int i = node[c].down; i != c; i = node[i].down) { for (int j = node[i].right; j != i; j = node[j].right) { remove(node[j].col); } ans[node[i].row] = 1; if (Dacing_Link_X()) { return true; } for (int j = node[i].left; j != i; j = node[j].left) { resume(node[j].col); } ans[node[i].row] = 0; } resume(c); return false; } int in_grid(int i, int j) { ++i; ++j; if (1 <= i && i <= 3 && 1 <= j && j <= 3) { return 1; } if (1 <= i && i <= 3 && 4 <= j && j <= 6) { return 2; } if (1 <= i && i <= 3 && 7 <= j && j <= 9) { return 3; } if (4 <= i && i <= 6 && 1 <= j && j <= 3) { return 4; } if (4 <= i && i <= 6 && 4 <=j && j <= 6) { return 5; } if (4 <= i && i <= 6 && 7 <= j && j <= 9) { return 6; } if (7 <= i && i <= 9 && 1 <= j && j <= 3) { return 7; } if (7 <= i && i <= 9 && 4 <= j && j <= 6) { return 8; } if (7 <= i && i <= 9 && 7 <= j && j <= 9) { return 9; } } void add(int i, int j, int k) { int x = (i * 9 + j) * 9 + k; mat[x][i * 9 + j] = 1; mat[x][81 + i * 9 + k] = 1; mat[x][162 + j * 9 + k] = 1; int g = in_grid(i, j); mat[x][243 + (g - 1) * 9 + k] = 1; } int main() { // printf("please enter your sudoku\n"); // while (~scanf("%s", su)) { if (!strcmp(su, "end")) { break; } most = 1000; memset (mat, 0, sizeof(mat)); init(324); int cur = 325; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (su[i * 9 + j] == '.') { for (int k = 0; k < 9; ++k) { add(i, j, k); } } else { int k = su[i * 9 + j] - '1'; add(i, j, k); } } } for (int i = 0; i < 729; ++i) { int s = cur; int pre = cur; for (int j = 0; j < 324; ++j) { if (!mat[i][j]) { continue; } int pos = j; node[cur].up = node[pos].up; node[node[pos].up].down = cur; node[cur].down = pos; node[pos].up = cur; node[cur].row = i; node[cur].col = pos; node[cur].left = pre; node[pre].right = cur; node[cur].right = s; cnt[pos]++; node[s].left = cur; pre = cur; cur++; } } Dacing_Link_X(); for (int i = 0; i < 81; ++i) { for (int j = 0; j < 9; ++j) { if (ans[i * 9 + j]) { printf("%d", j + 1); break; } } } printf("\n"); } return 0; }
POJ3074----Sudoku