首页 > 代码库 > POJ3074----Sudoku

POJ3074----Sudoku

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,

.2738..1.
.1...6735
.......29
3.5692.8.
.........
.6.1745.3
64.......
9518...7.
.8..6534.

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

Stanford Local 2006

把数独问题转成精确覆盖,课设要做这个就来学了下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