数独算法c
Ⅰ 基于SAT的数独游戏求解程序，求C语言代码
用0代表要填的数
#include <stdio.h>
#include <stdlib.h>
#define SIZE 9
#define get_low_bit(x) ((~x&(x-1))+1)
struct{
int left;
char num;
char try;
}board[SIZE][SIZE];
int bit2num(int bit)
{
switch(bit){
case 16:
case 256:
return 9;
基础解法
排除法（摒除法）
摒除法：用数字去找单元内唯一可填空格，称为摒除法，数字可填唯一空格称为排除法 (Hidden Single)。
根据不同的作用范围，摒余解可分为下述三种：
数字可填唯一空格在“宫”单元称为宫排除（Hidden Single in Box），也称宫摒除法。
数字可填唯一空格在“行”单元称为行排除法（Hidden Single in Row），也称行摒除法。
Ⅱ 计算数独有什么方法
数独（すうどく，Sūdoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
【基本方法】
解题的本质有二：隐性唯一解（Hidden Single）及显性唯一解（Naked Single），他们的名称是在候选数法的基础上命名的。
解题必须以逻辑为依归，猜测的方法被称为“暴力型”解法（Brute Force），这不是提倡数独的本意。
根据解题本质发展出来的基本解题方法有二种：
摒除法
摒除法：用数字去找单元内唯一可填空格，称为摒除法，数字可填唯一空格称为摒余解（隐性唯一解）。
根据不同的作用范围，摒余解可分为下述三种：
数字可填唯一空格在“宫”单元称为宫摒余解（Hidden Single in Box），这种解法称宫摒除法。
数字可填唯一空格在“行”单元称为行摒余解（Hidden Single in Row），这种解法称行摒除法。
数字可填唯一空格在“列”单元称为列摒余解（Hidden Single in Column），这种解法称列摒除法。
行摒余解和列摒余解合称行列摒余解（Hidden Single in Line）。
得到行列摒余解的方法称为行列摒除法。
余数法
Peer等位群格位
余数法：用格位去找唯一可填数字，称为余数法，格位唯一可填数字称为唯余解（Naked Single）。
余数法是删减等位群格位（Peer）已出现的数字的方法，每一格位的等位群格位有 20 个。
依解题填制的过程可区分为直观法与候选数法。
直观法
直观法就是不做任何记号，直接从数独的盘势观察线索，推论答案的方法。
候选数法
候选数法就是删减等位群格位已出现的数字，将剩余可填数字填入空格做为解题线索的参考，可填数字称为候选数（Candidates，或称备选数）。
直观法和候选数法只是填制时候是否有注记的区别，依照个人习惯而定，并非鉴定题目难度或技巧难度的标准，无论是难题或是简单题都可上述方法填制，一般程序解题以候选数法较多。
【进阶解法】
上述方法称为基础解法（Basic Techniques），其他所有的解法称为进阶解法（Advanced Techniques），是在补基本解法之不足，所以又称辅助解法。
进阶解法包括：区块摒除法（Locked Candidates）、数组法（Subset）、四角对角线（X-Wing）、唯一矩形（Unique Rectangle）、全双值坟墓（Bivalue Universal Grave）、单数链（X-Chain）、异数链（XY-Chain）及其他数链的高级技巧等等。已发展出来的方法有近百种之多。
其中前两种加上基础解法为一般数独书中介绍并使用的方法，同时也是大部分人可以理解并掌握的数独解题技法。
通过基础解法出数只需一种解法，摒除法或唯余法，超出此范围而需要施加进阶解法时，解题点需要进阶解法协助基础解法来满足隐性唯一或显性唯一才能出数，该解题点的解法需要多个步骤协力完成，因此称做组合解法。
相对概率
相对概率不是真实的概率，而是用于同一格中的几个数字之间相互比较出现的可能。
相对概率 = 九宫格出现的概率 × 行出现的概率 × 列出现的概率
九宫格出现的概率：如果九宫格中有2个格可能出现1，目标格可能的数字为1、2、3，另一个格可能出现的数字为1、4，那么：目标格中的1在九宫格出现的概率 = 目标格中出现1的概率 × (1 - 另一个格中出现1的概率)，得1/3 × (1-1/2) = 1/6。
注意：1-1/2表示另一个格不出现1的概率，1/3 × (1-1/2) 的意思就是在另一个格不出现1的情况下，目标格出现1的概率。
如果九宫格中有三个格可能出现1，目标格可能的数字为1、5、6，另一个格可能出现的数字为1、7，还有一个格可能出现的数字为1、8、9，得1/3 × (1-1/2) × (1-1/3) = 1/9。依此类推。
行出现的概率和列出现的概率与九宫格出现的概率的算法原理相同。最后，把三个概率相乘，得到相对概率，把目标格中3个数字的相对概率进行对比，相对概率越大，出现的可能性越大。
区块摒除法
区块摒除法包括宫区块摒除法（Pointing）与行列区块摒除法（Claiming）。
在基础题里，利用区块摒除可以替代一些基础解法的观察，或辅助基础解法寻找焦点。
在非基础题里，区块可以隐藏任何其他结构，简单的可以把基础解法隐藏起来，难的可以隐藏数对等等其他进阶技巧。
例如：
区块摒除法
首先数字6对第五宫摒除，得到第五宫的6在R4C5或者R6C5。
不论是在R4C5或者R6C5，C5的其他格都不能再有数字6。（R4C5与R6C5就是数字6的区块，这也是区块摒除作用的观点）
数字6对第二宫摒除，得解R1C4=6。
Ⅲ 数独万能解法数独口诀是什么
九宫格数独口诀是戴九履一，左三右七，二四有肩，八六为足，五居中央。还有口诀：“一居上行正中央，依次斜填切莫忘；上出框时向下放，右出框时向左放；排重便在下格填，右上排重一个样。” 这口诀不仅适用于九宫，也适用于推广的奇数九宫，如五五图，七七图等。
余数法：用格位去找唯一可填数字，称为余数法，格位唯一可填数字称为唯余解 。余数法是删减等位群格位（Peer）已出现的数字的方法，每一格位的等位群格位有 20 个。
直观法：直观法就是不做任何记号，直接从数独的盘势观察线索，推论答案的方法。
摒除法：用数字去找单元内唯一可填空格，称为摒除法，数字可填唯一空格称为摒余解 。数字可填唯一空格在“宫”单元称为宫摒余解，这种解法称宫摒除法。
如果这些数字的每一个区域、每一行、每一列都是1到9之间的数字，那么玩家需要使用一些排除、链删除等算法来填充整个9*9的地图，那么在游戏开始的时候，会有一些数字，而且这些数字是不能移动和删除的哦，这是游戏的难度等级，如果难度越大就意味着有更多的固定数字。
Ⅳ 数独高级解法有哪些
具体如下：
1、联除法：在两行三个隔膜中查找相同的数字，然后用它们查找另一行中的位数。该方法适用于中、高级数独。
2、巡格法：找出每个横膈膜数字的频率，找出它的位置。
3、排它法：这种方法是解决问题的关键，容易被普通老百姓所忽视。观察队列或横膈膜，如果有一个位置不能被其他数字填补，填补剩下的数字。
4、待定法：这种方法不常使用，但很有效。在区域中临时定位一个数字，并将其用于排除。
5、行列法：该方法用于提高破阶求解问题的效率。
6、假设法：作为专家，我并不主张这种做法。
7 、频率法：这种方法比以前的方法更有效。列出行中或框中的所有情况，然后选择一个高频率的数字。
8、用候选方法解决数独问题的候选算法首先，必须建立一个候选列表。在不同的条件下，每个宫格不可能的候选人可以逐步和安全地被清除。
候选数方法可以用来解决复杂的数独问题，但是候选数方法的使用不像直觉方法那样直接，需要建立候选人名单的准备过程，所以实际使用可以先用可视化方法解决问题，而不能用候选人的方法来解决问题。
候选人数方法的解决方法是逐步排除不合适候选数的过程，所以在删除候选数时一定要小心，要确定删除的候选人是否安全，否则，多次都要重做的问题。在电脑软件的帮助下，使得候选数表的维护变得轻松起来。
常规解题手法：
依解题填制的过程可区分为直观法与候选数法。
直观法就是不做任何记号，直接从数独的盘势观察线索，推论答案的方法。
候选数法就是删减等位群格位已出现的数字，将剩余可填数字填入空格做为解题线索的参考，可填数字称为候选数(Candidates，或称备选数)。
直观法和候选数法只是填制时候是否有注记的区别，依照个人习惯而定，并非鉴定题目难度或技巧难度的标准，无论是难题或是简单题都可上述方法填制，一般程序解题以候选数法较多。
Ⅳ 数独的计算公式是什么
1、联除法。
在并排的三个九宫格中的两排寻找相同数字，再利用九宫格得出另一排中该数字位置,该方法适用于中高级数独.
2、巡格法
找出在每个九宫格中出现频率较高的数字，得出该数字在其余九宫格内位置,该方法应用于方法一之后。
3、排除法
这个方法是解决问题的关键，易被常人所忽略。在各行列或九宫格中观察,若有个位置其它数字都不能填，就填余下的数字
4、待定法
此方法不常用却很有效。暂时确定某个数字在某个区域,再利用其来进行排除
5、行列法
此方法用于收官阶段，利用先从行列突破来提高解题效率。
6、假设法
即在某个位置随机的填上一个数字，再进行推演,并有可能最终产生矛盾而否定结论。
7、频率法
这种方法相比于上一种方法更能提高效率。在某一行列或九宫格列举出所有情况，再选择某位置中出现频率高的数字
8、候选数法
使用候选数法解数独题目需先建立候选数列表，根据各种条件，逐步安全的清除每个宫格候选数的不可能取值的候选数，从而达到解题的目的。
(5)数独算法c扩展阅读：
数独的出题方法：
1、挖洞法
从有到无的出题方法。先生成一个终盘，然后挖去部分数字形成一道题目。
2、填数法
从无到有的出题方法。在一个空盘面上填上部分数字形成一道题目。2007年日本NPGenerator软件的网站提出了一种边推理边出题的出题法，可以手工打造出漂亮图案的数独题目。
Ⅵ 用C语言如何随机生成一个数独
数独生成算法？这个还真不好搞，不过我当初写数独游戏的时候随便捣鼓出来过一个，你自己去改改吧，至于这个算法能不能生成所有的数独，我还真没论证过。
原理：对一个给出的数独棋盘的所有行或列交换给出的两个数X、Y，数组仍满足数独规则。如给出1、2，则对所有列交换1、2的位置，数组仍满足数独规则。
由于对棋盘的演进是随机的，所以相当于随机生成数独棋盘啦。每次演进的次数最好大一点，10次以上吧，以保证每个数都被换过位置。
具体代码就不用我写了吧，嘎嘎……
Ⅶ 求解数独题，用C语言实现
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
#include<stdio.h>
intmap[9][9];
boolisPlace(intcount){
introw=count/9;
intcol=count%9;
intj;
//同一行
for(j=0;j<9;++j){
if(map[row][j]==map[row][col]&&j!=col){
returnfalse;
}
}
//同一列
for(j=0;j<9;++j){
if(map[j][col]==map[row][col]&&j!=row){
returnfalse;
}
}
//同一小格
inttempRow=row/3*3;
inttempCol=col/3*3;
for(j=tempRow;j<tempRow+3;++j){
for(intk=tempCol;k<tempCol+3;++k){
if(map[j][k]==map[row][col]&&j!=row&&k!=col){
returnfalse;
}
}
}
returntrue;
}
voidbacktrace(intcount){
if(count==81){
for(inti=0;i<9;++i){
for(intj=0;j<9;++j){
printf("%d",map[i][j]);
}
printf("\n");
}
return;
}
introw=count/9;
intcol=count%9;
if(map[row][col]==0){
for(inti=1;i<=9;++i){
map[row][col]=i;//赋值
if(isPlace(count)){//可以放
backtrace(count+1);//进入下一层
}
}
map[row][col]=0;//回溯
}else{
backtrace(count+1);
}
}
intmain()
{
charc;
for(inti=0;i<9;i++)
{
for(intj=0;j<9;j++)
{
scanf("%c",&c);
if(c=='.')map[i][j]=0;
elsemap[i][j]=c-'0';
}
scanf("%c",&c);//接收换行符
}
backtrace(0);
return0;
}
Ⅷ 如何用C解9*9数独，求代码，高手勿喷。
int i, j, n=3; int col = 1, line = 0; a[line][col] = 1"%d ", a[i][j]); printf("\\n"); } return 0; } 我有解
Ⅸ 数独的计算公式是什么
数独的计算公式是每一横行、每一竖行和每一斜行的和都等于15。
Ⅹ 数独怎么玩 数独游戏的基本解法
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
解题手法
依解题填制的过程可区分为直观法与候选数法。
直观法就是不做任何记号，直接从数独的盘势观察线索，推论答案的方法。
候选数法就是删减等位群格位已出现的数字，将剩余可填数字填入空格做为解题线索的参考，可填数字称为候选数(Candidates，或称备选数)。
直观法和候选数法只是填制时候是否有注记的区别，依照个人习惯而定，并非鉴定题目难度或技巧难度的标准，无论是难题或是简单题都可上述方法填制，一般程序解题以候选数法较多。
摒除法
摒除法：用数字去找单元内唯一可填空格，称为摒除法，数字可填唯一空格称为摒余解(Hidden Single)。
根据不同的作用范围，摒余解可分为下述三种：
数字可填唯一空格在“宫”单元称为宫摒余解（Hidden Single in Box），这种解法称宫摒除法。
数字可填唯一空格在“行”单元称为行摒余解（Hidden Single in Row），这种解法称行摒除法。
数字可填唯一空格在“列”单元称为列摒余解（Hidden Single in Column），这种解法称列摒除法。
行摒余解和列摒余解合称行列摒余解（Hidden Single in Line）。
得到行列摒余解的方法称为行列摒除法。
余数法
Peer等位群格位
余数法：用格位去找唯一可填数字，称为余数法，格位唯一可填数字称为唯余解（Naked Single）。
余数法是删减等位群格位（Peer）已出现的数字的方法，每一格位的等位群格位有 20 个，如图七所示。
进阶解法
上述方法称为基础解法（Basic Techniques），其他所有的解法称为进阶解法（Advanced Techniques），是在补基本解法之不足，所以又称辅助解法。
进阶解法包括：区块摒除法（Locked Candidates）、数组法（Subset）、四角对角线（X-Wing）、唯一矩形（Unique Rectangle）、全双值坟墓（Bivalue Universal Grave）、单数链（X-Chain）、异数链（XY-Chain）及其他数链的高级技巧等等。已发展出来的方法有近百种之多。
其中前三种加上基础解法为一般数独书中介绍并使用的方法，同时也是大部分人可以理解并掌握的数独解题技法。
通过基础解法出数只需一种解法，摒除法或唯余法，超出此范围而需要施加进阶解法时，解题点需要进阶解法协助基础解法来满足隐性唯一或显性唯一才能出数，该解题点的解法需要多个步骤协力完成，因此称做组合解法。
解题必须以逻辑为依归，猜测的方法被称为暴力型解法(Brute Force)，这不是提倡数独的本意。
区块摒除法
区块摒除法包括宫区块摒除法（Pointing）与行列区块摒除法（Claiming）。
在基础题里，利用区块摒除可以替代一些基础解法的观察，或辅助基础解法寻找焦点。
在非基础题里，区块可以隐藏任何其他结构，简单的可以把基础解法隐藏起来，难的可以隐藏数对等等其他进阶技巧。
区块摒除法
首先数字6对第五宫摒除，得到第五宫的6在R4C5或者R6C5。
不论是在R4C5或者R6C5，C5的其他格都不能再有数字6。（R4C5与R6C5就是数字6的区块，这也是区块摒除作用的观点）
数字6对第二宫摒除，得解R1C4=6。
数对法
当一个单元（行、列、宫）的某两个数字仅可能在某两格时，我们称这两个格为这两个数的数对（Pairs）。
数对出现在宫称为宫数对；数对出现在行列成为行列数对。
用候选数法的观点去看，数对有两种，一种是在同单元内其中两格有相同的双候选数，一看就明白，因此称为显性数对（Naked Pair），另一种是，同单元内有两个候选数占用了相同的两格，该两格因为还有其它候选数很难辨认，因此称为隐性数对（Hidden Pair）。