一，标准数独（规则数独）

1，规则

2，隐含规则

3，对称性

4，斜线数独

二，标准数独校验、求解

力扣 36. 有效的数独

POJ 3074 Sudoku

POJ 2676 Sudoku

HDU 1426 Sudoku Killer

力扣 37. 解数独

CSU 内部题数独游戏（2017年院赛F题）

三，湖南省首届高校联合数独大赛

四，常用方法

1，摒除法

（1）摒除法

（2）宫内区块对行列摒除

（3）行列区块对宫摒除

（4）数对摒除

（5）三数组摒除

（6）显性数对

（7）数对占位

（8）显性三数组

（9）三元数组占位

（10）四数组摒除

（11）显性四数组

2，鱼结构

（1）X-Wing

（2）剑鱼

（3）水母

（4）多宝鱼

（5）空矩形

（6）2-String Kite

（7）摩天楼

3，外鳍

（1）外鳍 X-Wing

（2）外鳍剑鱼

（3）外鳍水母

（4）外鳍弗兰肯鱼

（5）外鳍退化 X-Wing

（6）外鳍退化剑鱼

（7）外鳍退化水母

4，唯一矩形

（1）可避免唯一矩形1型

（2）唯一矩形摒除

（3）唯一矩形2型

（4）唯一矩形4型

（5）唯一矩形6型

（6）唯一矩形1型

（7）可避免唯一矩形2型

（8）唯一矩形3型

（9）唯一矩形5型

5，else

（1）SDC

（2）W-Wing

（3）BUG+1

（4）XY-Wing

（5）XYZ-Wing

（6）ALS-XY-Wing

（7）X链

（8）ALS链

（9）远程数对

（10）XY链

（11）ALS-XZ链

一，标准数独（规则数独）

1，规则

数独盘面是个九宫，每一宫又分为九个小格。（宫即3*3的正方形）

在这八十一格中给出一定的已知数字，利用逻辑和推理，在其他的空格上填入1-9的数字。

使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

2，隐含规则

标准数独有一个隐含的规则，就是根据所给的数字，必须有且只有一个解。

在这个前提下，可以证明，至少需要给出17个数字。

17个数字的数独也不难设计出来，下面的题目中就有。

3，对称性

规则数独，对称性自然只能指数字的位置分布了。

规则数独和不规则数独在数字的分布上其实差别不大，也是那几种对称性，后面给出了一个示例。

相对而言，规则数独要想给出对称的位置分布的初始局面，比较简单。

而且因为格子画的本身就很对称，所以整体看起来很对称，这一点，不规则数独一般都做不到。

还有斜线数独也有很强的对称性。

4，斜线数独

这个数独看起来给的数也不少了，有27个，但是很难。

想了半天，一个都推不出来，还好我有下面的代码。

输入：

2..8..6..
.6..2..9.
..4..6..7
1..6..9..
.7..3..8.
..9..5..1
5..4..3..
.1..5..4.
..2..8..9

输出：

293817654
761524893
854396127
138642975
475931286
629785431
587469312
916253748
342178569

这就是这个数独的解了。

二，标准数独校验、求解

力扣 36. 有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:

输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。

class Solution {
public:bool ok(vector<vector<char>>& board, int i, int j, int k){for (int jj = 0; jj < 9; jj++)if (jj!=j && board[i][jj] == k)return false;for (int ii = 0; ii < 9; ii++)if (ii!=i && board[ii][j] == k)return false;int x = i / 3 * 3, y = j / 3 * 3;for (int ii = x; ii < x + 3; ii++)for (int jj = y; jj < y + 3; jj++)if ((ii!=i||jj!=j) && board[ii][jj] == k)return false;return true;}bool isValidSudoku(vector<vector<char>>& board) {for(int i=0;i<board.size();i++){for(int j=0;j<board[0].size();j++){if(board[i][j]!='.' && !ok(board,i,j,board[i][j])){return false;}}}return true;}
};

POJ 3074 Sudoku

In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,

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

这个题目，就是直接输入标准数独，输出数独的解。

题目里面有说You may assume that each puzzle in the input will have exactly one solution.

实际上这是标准数独必须满足的规定。

代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;int list[10][10];
bool ok(int i, int j, int k)
{for (int jj = 1; jj < 10; jj++)if (list[i][jj] == k)return false;for (int ii = 1; ii < 10; ii++)if (list[ii][j] == k)return false;int x = (i - 1) / 3 * 3, y = (j - 1) / 3 * 3;for (int ii = x + 1; ii <= x + 3; ii++)for (int jj = y + 1; jj <= y + 3; jj++)if (list[ii][jj] == k)return false;return true;
}bool trys(int i, int j)
{if (j == 10){i++;j = 1;}if (i == 10)return true;if (list[i][j])return trys(i, j + 1);for (int k = 1; k < 10; k++){if (ok(i, j, k)){list[i][j] = k;if (trys(i, j + 1))return true;}}list[i][j] = 0;return false;
}int main()
{char c,s[100];while (1){scanf("%s", &s);if (s[0] == 'e')return 0;for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++){c = s[i * 9 + j - 10];if (c == '.')list[i][j] = 0;else list[i][j] = c - '0';}trys(1, 1);for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)printf("%d", list[i][j]);printf("\n");}return 0;
}

这个代码已经飞快了，解一个数独大概是几毫秒，然而还是超时了。

于是我用dancing links来做，AC了。

#include <iostream>
#include <vector>
#include <map>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
using namespace std;
class DancingLink
{
public:vector<int>rows;//覆盖选中的行，值的范围是从1到mDancingLink(int m, int n, int maxNum){this->m = m, this->n = n;rhead.resize(m + 1), nums.resize(n + 1);row.resize(maxNum), col.resize(maxNum);up.resize(maxNum), down.resize(maxNum), lef.resize(maxNum), rig.resize(maxNum);sc.resize(m), rows.resize(m);for (int i = 0; i <= n; i++){up[i] = i, down[i] = i;lef[i] = i - 1, rig[i] = i + 1;row[i] = 0, col[i] = i, nums[i] = 0;}lef[0] = n, rig[n] = 0, nums[0] = INT_MAX;scid = 0, rowsid = 0;key = n;for (int i = 0; i <= m; i++)rhead[i] = 0;}void push(int r, int c)//新增坐标在(r,c)的一个节点{row[++key] = r, col[key] = c;up[key] = c, down[key] = down[c];up[down[c]] = key, down[c] = key;if (rhead[r] == 0)rhead[r] = lef[key] = rig[key] = key;else{lef[key] = rhead[r], rig[key] = rig[rhead[r]];lef[rig[rhead[r]]] = key, rig[rhead[r]] = key;}nums[c]++;}bool dfs(){while (true) {if (rig[0] == 0) {rows.resize(rowsid);return true;}int c = min_element(nums.begin(), nums.end()) - nums.begin();del(c);while (c = down[c]) {if (c > n)break;reback(col[c]);c = sc[--scid];rowsid--;for (int j = rig[c]; j != c; j = rig[j])reback(col[j]);}sc[scid++]=c;//记录选中idrows[rowsid++]=row[c];for (int j = rig[c]; j != c; j = rig[j])del(col[j]);}return false;}
private:inline void del(int c)//删除第c列的所有元素和他们所在行的所有元素{lef[rig[c]] = lef[c], rig[lef[c]] = rig[c];for (int i = down[c]; i != c; i = down[i])for (int j = rig[i]; j != i; j = rig[j])down[up[j]] = down[j], up[down[j]] = up[j], nums[col[j]]--;nums[c] = INT_MAX;}inline void reback(int c)//完全回退del操作{lef[rig[c]] = rig[lef[c]] = c, nums[c] = 0;for (int i = down[c]; i != c; i = down[i]) {for (int j = rig[i]; j != i; j = rig[j])down[up[j]] = up[down[j]] = j, nums[col[j]]++;nums[c]++;}}
private:int m, n, key;vector<int>row, col;//每个节点的行，列vector<int>rhead;//每行第一个节点的idvector<int>up, down, lef, rig;//每个节点上下左右的节点idvector<int>nums;//每一列的元素个数vector<int>sc;int scid, rowsid;
};string Sudoku(string s, char cEmpty = '.')
{int num = 0;for (int i = 0; i < 81; i++)if (s[i] != cEmpty)num++;int m = (81 - num) * 9 + num;int n = 81 * 4;DancingLink d(m, n, m * 4 + n + 5);int row = 0;map<int, int>mrow;mrow[0] = -1;for (int i = 0; i < 81; i++) {//第i个格子char c = s[i];int low = 0, high = 8;if (c != cEmpty)low = high = c - '1';//第i个格子的搜索值域for (int x = low; x <= high; x++) {d.push(++row, i + 1), d.push(row, i / 9 * 9 + x + 81 + 1);d.push(row, i % 9 * 9 + x + 162 + 1), d.push(row, (i / 27 * 3 + i % 9 / 3) * 9 + x + 243 + 1);mrow[row] = i;}}if (!d.dfs())return "";string ans = s;for (int i = 0; i < d.rows.size();i++) {int row = d.rows[i];int id = mrow[row];if (s[id] == cEmpty) {ans[id] = '1';while (mrow[row - 1] == id)ans[id]++, row--;}else ans[id] = s[id];}return ans;
}
int main()
{string s;while (cin>>s){if(s=="end")return 0;cout << Sudoku(s) << endl;}return 0;
}

POJ 2676 Sudoku

题目：

Description

Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.

Input

The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
Output

For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.
Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

代码：

#include<iostream>
using namespace std;int list[10][10];bool ok(int i, int j, int k)
{for (int jj = 1; jj < 10; jj++)if (list[i][jj] == k)return false;for (int ii = 1; ii < 10; ii++)if (list[ii][j] == k)return false;int x = (i - 1) / 3 * 3, y = (j - 1) / 3 * 3;for (int ii = x + 1; ii <= x + 3; ii++)for (int jj = y + 1; jj <= y + 3; jj++)if (list[ii][jj] == k)return false;return true;
}bool trys(int i, int j)
{if (j == 10){i++;j = 1;}if (i == 10)return true;if (list[i][j])return trys(i, j + 1);for (int k = 1; k < 10; k++){if (ok(i, j, k)){list[i][j] = k;if (trys(i, j + 1))return true;}}list[i][j] = 0;return false;
}void out()
{for (int i = 1; i < 10; i++){for (int j = 1; j < 10; j++)cout << list[i][j];cout << endl;}
}int main()
{char c;int n;cin >> n;while (n--){for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++){cin >> c;list[i][j] = c - '0';}trys(1, 1);out();}return 0;
}

HDU 1426 Sudoku Killer

初一看这名字，还以为是杀手数独，吓死了

题目：

Description

自从2006年3月10日至11日的首届数独世界锦标赛以后，数独这项游戏越来越受到人们的喜爱和重视。
据说，在2008北京奥运会上，会将数独列为一个单独的项目进行比赛，冠军将有可能获得的一份巨大的奖品―――HDU免费七日游外加lcy亲笔签名以及同hdu acm team合影留念的机会。
所以全球人民前仆后继，为了奖品日夜训练茶饭不思。当然也包括初学者linle，不过他太笨了又没有多少耐性，只能做做最最基本的数独题，不过他还是想得到那些奖品，你能帮帮他吗？你只要把答案告诉他就可以，不用教他是怎么做的。

数独游戏的规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。比如有这样一个题，大家可以仔细观察一下，在这里面每行、每列，以及每个3x3的方格都包含1-9这九个数字。

例题：

答案：

Input

本题包含多组测试，每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，问号（?）表示需要你填的数。
Output

对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。
对于每组测试数据保证它有且只有一个解。
Sample Input

7 1 2 ? 6 ? 3 5 8
? 6 5 2 ? 7 1 ? 4
? ? 8 5 1 3 6 7 2
9 2 4 ? 5 6 ? 3 7
5 ? 6 ? ? ? 2 4 1
1 ? 3 7 2 ? 9 ? 5
? ? 1 9 7 5 4 8 6
6 ? 7 8 3 ? 5 1 9
8 5 9 ? 4 ? ? 2 3
Sample Output

7 1 2 4 6 9 3 5 8
3 6 5 2 8 7 1 9 4
4 9 8 5 1 3 6 7 2
9 2 4 1 5 6 8 3 7
5 7 6 3 9 8 2 4 1
1 8 3 7 2 4 9 6 5
2 3 1 9 7 5 4 8 6
6 4 7 8 3 2 5 1 9
8 5 9 6 4 1 7 2 3
代码：

#include<iostream>
using namespace std;int list[10][10];bool ok(int i, int j, int k)
{for (int jj = 1; jj < 10; jj++)if (list[i][jj] == k)return false;for (int ii = 1; ii < 10; ii++)if (list[ii][j] == k)return false;int x = (i - 1) / 3 * 3, y = (j - 1) / 3 * 3;for (int ii = x + 1; ii <= x + 3; ii++)for (int jj = y + 1; jj <= y + 3; jj++)if (list[ii][jj] == k)return false;return true;
}bool trys(int i, int j)
{if (j == 10){i++;j = 1;}if (i == 10)return true;if (list[i][j])return trys(i, j + 1);for (int k = 1; k < 10; k++){if (ok(i, j, k)){list[i][j] = k;if (trys(i, j + 1))return true;}}list[i][j] = 0;return false;
}void out()
{for (int i = 1; i < 10; i++){for (int j = 1; j < 9; j++)cout << list[i][j]<<" ";cout << list[i][9] << endl;}
}int main()
{char c;int key = 0;while (cin>>c){if (key)cout << endl;key++;for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++){if(i>1||j>1)cin >> c;if (c == '?')list[i][j] = 0;else list[i][j] = c - '0';}trys(1, 1);out();}return 0;
}

力扣 37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

int list_[10][10];bool ok(int i, int j, int k)
{for (int jj = 1; jj < 10; jj++)if (list_[i][jj] == k)return false;for (int ii = 1; ii < 10; ii++)if (list_[ii][j] == k)return false;int x = (i - 1) / 3 * 3, y = (j - 1) / 3 * 3;for (int ii = x + 1; ii <= x + 3; ii++)for (int jj = y + 1; jj <= y + 3; jj++)if (list_[ii][jj] == k)return false;return true;
}bool trys(int i, int j)
{if (j == 10){i++;j = 1;}if (i == 10)return true;if (list_[i][j])return trys(i, j + 1);for (int k = 1; k < 10; k++){if (ok(i, j, k)){list_[i][j] = k;if (trys(i, j + 1))return true;}}list_[i][j] = 0;return false;
}class Solution {
public:void solveSudoku(vector<vector<char>>& board) {for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++){if(board[i-1][j-1]=='.')list_[i][j] = 0;else list_[i][j] = board[i-1][j-1] - '0';}trys(1, 1);for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++) board[i-1][j-1] = list_[i][j] + '0';}
};

CSU 内部题数独游戏（2017年院赛F题）

题目：

Problem Description

自从2006年3月10日至11日的首届数独世界锦标赛以后，数独这项游戏越来越受到人们的喜爱和重视。

Input

第一行输入一个整数T，代表共有T组数据，每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，数字0表示需要你填的数。

Output

对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。

对于每组测试数据保证它有且只有一个解。

Sample Input

7 1 2 0 6 0 3 5 8

0 6 5 2 0 7 1 0 4

0 0 8 5 1 3 6 7 2

9 2 4 0 5 6 0 3 7

5 0 6 0 0 0 2 4 1

1 0 3 7 2 0 9 0 5

0 0 1 9 7 5 4 8 6

6 0 7 8 3 0 5 1 9

8 5 9 0 4 0 0 2 3

Sample Output

7 1 2 4 6 9 3 5 8

3 6 5 2 8 7 1 9 4

4 9 8 5 1 3 6 7 2

9 2 4 1 5 6 8 3 7

5 7 6 3 9 8 2 4 1

1 8 3 7 2 4 9 6 5

2 3 1 9 7 5 4 8 6

6 4 7 8 3 2 5 1 9

8 5 9 6 4 1 7 2 3

我的代码：

#include<iostream>
using namespace std;int list[10][10];bool ok(int i, int j, int k)
{for (int jj = 1; jj < 10; jj++)if (list[i][jj] == k)return false;for (int ii = 1; ii < 10; ii++)if (list[ii][j] == k)return false;int x = (i - 1) / 3 * 3, y = (j - 1) / 3 * 3;for (int ii = x + 1; ii <= x + 3; ii++)for (int jj = y + 1; jj <= y + 3;jj++)if (list[ii][jj] == k)return false;return true;
}bool trys(int i, int j)
{if (j == 10){i++;j = 1;}if (i == 10)return true;if (list[i][j])return trys(i, j + 1);for (int k = 1; k < 10; k++){if (ok(i, j, k)){list[i][j] = k;if (trys(i, j + 1))return true;}}list[i][j] = 0;return false;
}void out()
{for (int i = 1; i < 10; i++){for (int j = 1; j < 9; j++)cout << list[i][j]<<" ";cout <<list[i][9]<< endl;}
}int main()
{int t;cin>>t;while(t--){for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)cin >>list[i][j];trys(1, 1);out();cout<<endl;}	return 0;
}

比赛的时候我带了好多以前打印的博客，其中HDU - 1426 Sudoku Killer里面的题目，其实就是这个题目原题。