数独数组解法,数独解题方法介绍

@(这里写自定义目录标题)

数独的编程求解

求解过程是用候选数求解法，用编程实现了唯一数求解、区块删除法和对数法。其它实现方法待实现后再写。

数据准备

用一个9*9的二维数组存储九宫格内数据，而每一个格子的数据用一个二进制表示。这里我采用了10位二进制，最低位作为候选数和已解数的标志，1标志其为候选数，0为已解数。其它9位表示1-9。例如1000000000表示已解数9，1100000001表示候选数9、8。

求候选数

首先第一步是求出所有的候选数，具体算法在代码中注释
求[x,y]格的候选数：

int temp = 1; //临时变量 for (int i = 0; i < 9; i++)//对所在行、列的已解数进行或运算 { if ((shu[x, i] & 1) == 0) //如果是已解数 { temp |= shu[x, i];//逐行 } if ((shu[i, y] & 1) == 0) //如果是已解数 { temp |= shu[i, y];//逐列 } } int gx = x / 3;//同宫 int gy = y / 3; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { if ((shu[gx * 3 + i, gy * 3 + j] & 1) == 0) //如果是已解数 { temp |= shu[gx * 3 + i, gy * 3 + j]; } } shu[x, y] = (~temp)&1023 ; //取反 取10位

例如x,y 所在的同行有5（100000）6（1000000）同列有3（1000）同宫内还有2（100）或运算后结果为1101100，取反并只取10位1110070011，代表9、8、7、4、1。

唯一解

从候选数解法上讲，唯一数有显式唯一数（上一步计算后，格子里只有一个候选数），隐式唯一数（在同行或同列、同宫内只出现一次的候选数）

显式唯一数 int w=-1;//如果唯一记下位置int j=0；for (int i= 0; i < 9; i++)//如果1的个数大于1 则候选数不唯一 { x >>= 1; if ((x & 1) == 1) { w = i; j++; if ( j> 1) { break; } } } 隐式唯一数

把同行或同列、同宫内其它所有数或运算，然后取反 ，统计1的出现次数，如果为1，则求出唯一数。

int baoliu = shu[x, y]; shu[x, y] = 1; //可以避免后面判断 int temp; //行唯一 { temp = 1; for (int i = 0; i < 9; i++)//行 { temp |= shu[x, i];//逐行 } temp = ~temp; if (WeiYi(temp) != -1) { shu[x, y] = baoliu; return temp; } }

如果是唯一解则退出，如果不是在分别看在同列、同宫内是不是唯一解。

区块删除法

如图，在4列中3只在上面宫中出现，所以3就不可能在上面这个宫中的其它列出现，可以把B5中的3删掉，5就是唯一数了。

for (int gx = 0; gx < 3; gx++)//gx 为宫坐标 { for (int j = 0; j < 9; j++) { int temp = 1; for (int i = 0; i < 9; i++) { if (i >= gx * 3 && i < gx * 3 + 3) { if ((shu[i, j] & 1) == 1)//该范围内候选数跳过 continue; } temp |= shu[i, j]; } if ((~temp & 1022) != 0) { //宫内其它列是否有temp int t = 0; for (int jkdmp = 0; jkdmp < 3; jkdmp++) { if (j == j/3*3+jkdmp) continue; for (int ii = 0; ii < 3; ii++) { t |= shu[gx * 3 + ii, j/3*3 + jkdmp]; } } t |= 1; if (((~temp & t)&1022)!= 0)//=0没有 如有 求解 { re[1] = j; re[2] = gx; re[3] = j / 3; re[4] = ~temp; re[5] = 1; return re; } } } }

这是按列计算，删除同宫候选数，同行、同宫也一样。

对数法

对数法也有两种，上图中H行 候选数7，9作为一对出现在H6、H9格内，那么7如果在H6，9必然在H9，或者反过来。H行其它格内的7和9都应删除。
这个图中2，9只出现在6列和7列，同行不含这两个数任意一个，则6列、7列中的7就该删除掉。
对数法实现起来比较麻烦，我先是把同行所有候选数进行组合，然后再依次判断。

private void duishu(int x, ref Queue<int> dui) { int temp; dui.Clear(); Queue<int> t = new Queue<int>(); for (int i = 1; i < 10; i++) { if ((x >> i & 1) == 1) t.Enqueue(1 << i); } while (t.Count >= 2) { temp = t.Dequeue(); foreach (int y in t) { dui.Enqueue(temp | y); } } }

这段代码是组合对数的

寻找只在两个格子中出现的一对数，如果同行列宫其他格内含有这对数中的一个或2个则需删除。

Queue<int> houxuanduishu = new Queue<int>(); int t = 0; for (int i = 0; i < 9; i++)//按行查找 { for (int j = 0; j < 9; j++) { if ((shu[i, j] & 1) == 1) { t |= shu[i, j]; } } duishu(t, ref houxuanduishu); int ji ; Point[] p = new Point[2]; foreach (int c in houxuanduishu) { t = c | 1; ji = 0; for (int j = 0; j < 9; j++) { if ((shu[i, j] & 1023) == t) { p[ji].X = i; p[ji].Y = j; ji++; } if (ji == 2) { bool ck = false; for (int jkdmp = 0; jkdmp < 9; jkdmp++) { if (jkdmp ==p[0].Y||jkdmp==p[1].Y) continue; if (((shu[i, jkdmp] & 1022) & t) != 0)//其它格是否含这对数 t含 { ck = true; ; break; } } if (ck) { ret[0] = p[0].X; ret[1] = p[0].Y; ret[2] = p[1].X; ret[3] = p[1].Y; ret[4] = t; ret[5] = 0; return ret; } } } }

第二中对数法，只有两个格含有这对数，且这两个格含有其它数，则需删除这两个内其它数。

foreach (int c in houxuanduishu) { ji = 0; t = c & 1022; for (int j = 0; j < 9; j++) { if (((shu[i, j] & 1022) & t) == t)//格是否含这对数 true含 { ji++; if (ji > 2) break; p[ji - 1].X = i; p[ji - 1].Y = j; ; } } int temp=0; if (ji == 2) { for(int j=0;j<9;j++) { if((j!=p[0].Y)&&(j!=p[1].Y)) temp |= shu[i, j]; } if ((temp & 1022 & t) != 0) { continue; } if ((shu[p[0].X, p[0].Y] & 1022) != t || (shu[p[1].X, p[1].Y] & 1022) != t)//这两个格含有其他数 { ret[0] = p[0].X; ret[1] = p[0].Y; ret[2] = p[1].X; ret[3] = p[1].Y; ret[4] = c; return ret; } }

通过依次使用这几种方法，一般难度的数独都可以解决。其它高级的方法待熟悉后再增加。