大家好，欢迎来到IT知识分享网。
目录
一，标准数独（规则数独）
1，规则
数独盘面是个九宫，每一宫又分为九个小格。（宫即3*3的正方形）
在这八十一格中给出一定的已知数字，利用逻辑和推理，在其他的空格上填入1-9的数字。
使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
2，隐含规则
标准数独有一个隐含的规则，就是根据所给的数字，必须有且只有一个解。
在这个前提下，可以证明，至少需要给出17个数字。
17个数字的数独也不难设计出来，下面的题目中就有。
3，对称性
规则数独，对称性自然只能指数字的位置分布了。
规则数独和不规则数独在数字的分布上其实差别不大，也是那几种对称性，后面给出了一个示例。
相对而言，规则数独要想给出对称的位置分布的初始局面，比较简单。
而且因为格子画的本身就很对称，所以整体看起来很对称，这一点，不规则数独一般都做不到。
还有斜线数独也有很强的对称性。
4，斜线数独
这个数独看起来给的数也不少了，有27个，但是很难。
想了半天，一个都推不出来，还好我有下面的代码。
输入：
输出：
这就是这个数独的解了。
二，标准数独校验、求解
力扣 36. 有效的数独
判断一个 9×9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
示例 1:
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
这个题目，就是直接输入标准数独，输出数独的解。
题目里面有说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到m DancingLink(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;//记录选中id rows[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;//每行第一个节点的id vector<int>up, down, lef, rig;//每个节点上下左右的节点id vector<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
题目：
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3×3 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 3×3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.
Input
#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
初一看这名字，还以为是杀手数独，吓死了
题目：
数独游戏的规则是这样的：在一个9×9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3×3的方格也同时包含1-9这九个数字。比如有这样一个题，大家可以仔细观察一下，在这里面每行、每列，以及每个3×3的方格都包含1-9这九个数字。
#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. 解数独
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
示例：
提示：
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日的首届数独世界锦标赛以后，数独这项游戏越来越受到人们的喜爱和重视。
数独游戏的规则是这样的：在一个9×9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3×3的方格也同时包含1-9这九个数字。比如有这样一个题，大家可以仔细观察一下，在这里面每行、每列，以及每个3×3的方格都包含1-9这九个数字。
Input
第一行输入一个整数T，代表共有T组数据，每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，数字0表示需要你填的数。
Output
对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。
对于每组测试数据保证它有且只有一个解。
Sample Input
1
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里面的题目，其实就是这个题目原题。
三，湖南省首届高校联合数独大赛
2015年5月9日，湖南省首届高校联合数独大赛在湘潭大学举行。
在此之前，五个学校都各自举办校内初赛，选拔出一些人参加湘潭的决赛。
初赛和决赛的比赛规则差不多，在规定时间内求解数独，按照填对的格子来计分，
对1个格子就是1分，错了或者不填不扣分。
下面是建模主页君的说说：
下面是题目和答案：
我基本上全部写出来了，对了多少就不知道了，成绩还行，初赛第五名。
然后5月9日，数模社团出钱买汽车票，周芳玉学姐带着我们八个去了湘潭。
那是我第一次去湘潭，特别开心。
去的时候，除了周学姐，基本上只和丁学长聊天。
他很厉害，是初赛第一名，在车上还看数独的书。
当然，我也做了很多准备，在决赛名额出来之后我刷了一个星期的不规则数独。
这么多数独，我确实是一个星期刷完的，主要是利用2个时间，
一个是下课时间，一个是离散数学课的时间。
费老师看到我做这些事情，什么也没说，还发了一个文件给我，里面有很多数独。
后来决赛的结果，丁学长第六名，我第八名，其他几个同学没有名次。
我没有初赛的获奖证书，但是有决赛的获奖证书，上面盖的是湘潭大学数学院的章子。
据说如果自己把这个证书拿去学社联盖章，是有综测加分的，
可惜我没有去，所以证书就没什么效用了，只当做纪念了。
前面的四个题目是自己做，评单人奖。
最后的武士数独是八个人一起做，评团队奖。
但是比赛之前并不知道会有武士数独，所以策略不对，做的一塌糊涂。
武士数独答案在前面有。
四，常用方法
这一章的内容来自业界良心：全民数独
1，摒除法
（1）摒除法
（2）宫内区块对行列摒除
（3）行列区块对宫摒除
（4）数对摒除
（5）三数组摒除
（6）显性数对
（7）数对占位
（8）显性三数组
（9）三元数组占位
（10）四数组摒除
（11）显性四数组
2，鱼结构
（1）X-Wing
从小学四年级开始做数独，一直是纸上做，后来才有手机电脑。
我的标记习惯是只标记很接近推出来的格子，比如某个格子的数字只能是2种情况。
所以只有X-Wing经常用，剑鱼和水母应该没用过。
（2）剑鱼
（3）水母
没太理解，为什么一定有互补的小鱼。（话说怎么才算互补？行列分别互补吗？不太懂）
（4）多宝鱼
（5）空矩形
（5.1）标准模式
（5.2）含有2个候选数的空矩形
（5.3）双空矩形
（6）2-String Kite
（6.1）标准模式
（6.2）双重2-String Kite
（7）摩天楼
3，外鳍
（1）外鳍 X-Wing
（2）外鳍剑鱼
（3）外鳍水母
（4）外鳍弗兰肯鱼
（5）外鳍退化 X-Wing
（6）外鳍退化剑鱼
（7）外鳍退化水母
4，唯一矩形
唯一矩形（UR）指的是下面的结构，数独的隐含规则是数独不能出现这种情况。
如果把这个限制作为数独的条件，可以得到唯一矩形系列方法。
（1）可避免唯一矩形1型
（2）唯一矩形摒除
（3）唯一矩形2型
（4）唯一矩形4型
（5）唯一矩形6型
（6）唯一矩形1型
（7）可避免唯一矩形2型
（8）唯一矩形3型
（9）唯一矩形5型
5，else
（1）SDC
（1.1）基本形态
（1.2）拓展类型
（2）W-Wing
（3）BUG+1
（4）XY-Wing
（5）XYZ-Wing
（6）ALS-XY-Wing
ALS是almost locked set
（7）X链
（8）ALS链
（9）远程数对
（10）XY链
（11）ALS-XZ链
（11.1）单链
（11.2）双链
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/136228.html
