Sudoku
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
我的代码
这一题直接暴力搜是会超时的，自己改了好几次依旧过不了，只能把所有的都推倒重新来。上网查了一下是需要快速失败的方式搜索，也就是每次递归都选一个可选数字最少的来递归。不过实现的方法也挺讲究的，我一开始的代码往这方面改就依旧过不掉。
#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)
此题用舞蹈链做法极快无比，可惜我看了一上午愣是没看懂，先标记一下以后再看。
算法介绍在这里点击这里
本题具体实现方法在这里点击这里
反思
以后搜索时也要多多利用快速失败法。