算法

POJ3074总结

Sudoku

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

我的代码

这一题直接暴力搜是会超时的,自己改了好几次依旧过不了,只能把所有的都推倒重新来。上网查了一下是需要快速失败的方式搜索,也就是每次递归都选一个可选数字最少的来递归。不过实现的方法也挺讲究的,我一开始的代码往这方面改就依旧过不掉。

#include<stdio.h>
#include<string.h>
char s[100];
int values[81][10];//values[i][j]:对于数独第i号方块values[i][0]表示其可选择的数,values[i][j]表示是否可选数字j 
bool assign(int values[][10],int grid, int value);
void printSudoku()
//输出结果 
{
	int i = 0;
	while (i < 81)
	{
		printf("%c", s[i]);
		i++;
	}
	printf("\n");
}
void copyvalues2sudoku(int values[][10])
//将整理好的每一块的数字情况转换成数独 
{
	for (int i = 0; i < 81; ++i)
	{
		for (int n = 1; n <= 9; ++n)
		{
			if (values[i][n])
			{
				s[i] = (char)(n+'0');
				break;
			}
		}
	}
}
 
bool remove(int values[][10], int grid, int value)
//将指定块grid的数字value禁用 
{
	if (values[grid][value] == 1)
	{
		values[grid][value] = 0;
		values[grid][0]--;
		if (values[grid][0] < 1)
		{
			return false;
		}
		else if (values[grid][0] == 1)
		{
			for (int n = 1; n <= 9; ++n)
			{
				if (values[grid][n] != 0)
				{
					if (!assign(values, grid, n))
					{
						return false;
					}
					break;
				}
			}
		}
		return true;
	}
	else {
		return true;
	}
}
 
bool assign(int values[][10], int grid, int value)
//根据给定块grid的值value,更新与其同行、同列、同组的块可选数字范围 
{
	values[grid][0] = 1;
	for (int n = 1; n <= 9; ++n)
	{
		values[grid][n] = 0;
	}
	values[grid][value] = 1;
 	//行 
	int r = grid / 9, c = grid % 9;
	for (int i = 0; i < 9; ++i)
	{
		int g = r * 9 + i;
		if (g != grid && !remove(values, g, value))
		{
			return false;
		}
	}
	//列 
 	for (int i = 0; i < 9; ++i)
	{
		int g = i * 9 + c;
		if (g != grid && !remove(values, g, value))
		{
			return false;
		}
	}
	//组 
 	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			int g = (r / 3 * 3 + i) * 9 + (c / 3 * 3 + j);
			if (g != grid && !remove(values, g, value))
			{
				return false;
			}	
		}		
	}
	return true;
}
 
bool search(int values[][10])
//选择可能情况最少的数字进行搜索 
{
	bool allone = true;
	int mini = 0, minn = 9;
	for (int i = 0; i < 81; ++i)
	//选择可选数字最少的块mini 
	{
		if (values[i][0] != 1)
		{
			allone = false;
			if (values[i][0] < minn)
			{
				mini = i;
				minn = values[i][0];
			}
		}
	}
 	if (allone)
 	//递归出口:当所有块只有一种情况时可以输出了 
	{
		copyvalues2sudoku(values);
		return true;
	}
	int valuescopy[81][10];//搜索过程中生成的一种可能情况 
	for (int n = 1; n <= 9; ++n)
	{
		if (values[mini][n])
		{
			for (int i = 0; i < 81; ++i)
			{
				for (int n = 0; n <= 9; ++n)
				{
					valuescopy[i][n] = values[i][n];
				}
			}
			if (assign(valuescopy, mini, n))
			//对刚刚找到的mini进行递归 
			{
				if (search(valuescopy))
				{
					return true;	
				}
			}
			values[mini][0]--;
			values[mini][n] = false;
		}
	}
 
	return false;
}
int main()
{
	scanf("%s",s);
	while (strcmp(s,"end")!=0)
	{
		memset(values,0,sizeof(values));
		for (int i = 0; i < 81; i++)
		//对每一块的可选数字情况进行初始化 
		{
			if (s[i] == '.')
			{
				values[i][0] = 9;
				for (int n = 1; n <= 9; ++n)
				{
					values[i][n] = 1;
				}
			}
			else
			{
				values[i][0] = 1;
				for (int n = 1; n <= 9; ++n)
				{
					values[i][n] = 0;
				}
				values[i][(int)(s[i]-'0')] = 1;
			}
		}
		for (int i = 0; i < 81; ++i)
		//根据已经确定的数字来更新未确定块的可选情况 
		{
			if (s[i] != '.')
			{
				assign(values,i,(int)(s[i]-'0'));
			}
		}
		search(values);
		printSudoku();
		scanf("%s",s);
	}
	return 0;
}

舞蹈链(Dancing Link)

此题用舞蹈链做法极快无比,可惜我看了一上午愣是没看懂,先标记一下以后再看。

算法介绍在这里点击这里

本题具体实现方法在这里点击这里

反思

以后搜索时也要多多利用快速失败法。

发表评论