数独算法
一 知识背景
无
二 绪言
偶尔玩下休闲益智小游戏，一方面可以舒解下心情，另一方面刺激下大脑皮层。百度了一下数独 的起源和概念。说了那么多，看着就累。精简一下就是数字（0-9）填充游戏。不明白的来一张大图。看到了吧，就这样子滴~，先有个直观印象吧。
数独图片
三 规则
往简单点说就3条：
1.每个横列需要1~9数值填充，不能重复。
2.每个纵列需要1~9数值填充，不能重复。
3.每个小的九方格里面需要1~9数值填充，不能重复。
横，纵，小九方格 说明
四 算法分析
首先要写出这个算法，需要清楚里面的规则。数值可以用9*9的坐标来表示，x,y坐标在编程语言里面可以用对象，数组等来表示。我在这里选用的数据结构有数组，栈。将算法分解一下，可以得到如下几块：
1.用数组[0][0],[8][8]来表示大的九宫格，空白区域代表数值0。
2 小九宫格与九个坐标的关系3n~3n+2，横纵都是如此。
_0_0 （n=0）代表第一个 ，里面有九个坐标：
（0,0）（0,1）（0,2）
（1,0）（1,1）（1,2）
（2,0）（2,1）（2，2）
_0_1 (n=1)代表第二个 ，里面有九个小坐标
（0,3）（0,4）（0,5）
（1,3）（1,4）（1,5）
（2,3）（2,4）（2，5）
。
。
。
其他类推.
3.规则
横，纵，小方格，数值1~9值都填满，不重复。
4.判断算法执行完成
数组里面的值加起来为 9*（1+2+3+4+5+6+7+8+9） = 405 即可。
5. 根据3规则得到每个空点（也就是数值为0的）坐标有几个，然后依次递归调用，直到使数组最后的值为405退出。
五.部分代码参考
//横纵坐标校验规则
public static booleanXYRule(intx, inty, int[][] a, intresult) {
if(x >8|| x <0) {
return false;
}
if(y <0|| y >8) {
return false;
}
for(inti =0;i <9;i++) {//横坐标校验
if(a[x][i] == result) {
return false;
}
}
for(inti =0;i <9;i++) {//纵坐标校验
if(a[i][y] == result) {
return false;
}
}
return true;
}
//小九宫格校验
public static booleanlitterBoxRule(intx, inty, int[][] a, intresult,Map> map) {
List enumValues =getCoordinateEnumValue(x,y,map);
for(Coordinate coordinate : enumValues) {
if(a[coordinate.getX()][coordinate.getY()] == result) {
return false;
}
}
return true;
}
//判断是否完成
public static booleanfinish(inta[][]) {
int sum =0;
for(inti =0;i <9;i++) {
for(intj =0;j <9;j++) {
sum += a[i][j];
}
}
if(sum ==405) {
return true;
}
return false;
}
//得到一个有效的坐标点， 1.若果小九宫格已经有八个了，返回第九个坐标点，2找到横纵轴立面空白最少的返回
public staticCoordinatefindFirst(int[][] a,Map> map) {
for(Map.Entry entry : map.entrySet()) {
int count =0;
Coordinate coordinate1 =newCoordinate();
for(Coordinate coordinate : (List) entry.getValue()) {
if(a[coordinate.getX()][coordinate.getY()] !=0) {
count++;
}else{
coordinate1 = coordinate;
}
}
if(count ==8) {
return coordinate1;
}
}
intx[] =new int[9];
inty[] =new int[9];
for(inti =0;i <9;i++) {
for(intj =0;j <9;j++) {
if(a[i][j] !=0) {
x[i]++;
}
if(a[j][i] !=0) {
y[i]++;
}
}
}
Coordinate maxA =findMax(x);
Coordinate maxB =findMax(y);
if(maxA.getX() < maxB.getX()) {
intindexY = maxB.getY();
for(inti =0;i <9;i++) {
if(a[i][indexY] ==0) {
Coordinate coordinate1 =newCoordinate(i,indexY);
return coordinate1;
}
}
}else{
intindexX = maxA.getY();
for(inti =0;i <9;i++) {
if(a[indexX][i] ==0) {
Coordinate coordinate1 =newCoordinate(indexX,i);
return coordinate1;
}
}
}
return null;//执行到这说明数值已经填充完了
}
//递归调用，找到相应的值进行填充，用栈来保存每一步，就和迷宫问题（数据结构一种案例）一样
public static voidfindBestValue(Coordinate coordinate, int[][] a,Map> map,StackList stackList) {
List list =findRightValue(coordinate,a,map);
for(Integer s : list) {
if(!stackList.empty()) {
if(finish(a)) { //执行完成
return;
}
Coordinate peek =null;
peek = (Coordinate) stackList.peek();
if(peek.getX() != coordinate.getX() || peek.getY() != coordinate.getY()) {//没有就填充进去
stackList.push(coordinate);
}
}
if(stackList.empty()) {
stackList.push(coordinate);
}
a[coordinate.getX()][coordinate.getY()] = s;
Coordinate coordinate1 = SudoKuUtils.findFirst(a,map);
if(coordinate1 ==null) {
return;
}
List list2 =findRightValue(coordinate1,a,map);
if(list2.size() ==0) {
if(!stackList.empty()) {
Coordinate coordinate2 = (Coordinate) stackList.peek();
a[coordinate2.getX()][coordinate2.getY()] =0;
coordinate = (Coordinate) stackList.pop();
}
}else{
findBestValue(coordinate1,a,map,stackList);
}
}
if(!stackList.empty()) {
Coordinate coordinate2 = (Coordinate) stackList.peek();
if(coordinate.getX() == coordinate2.getX() && coordinate.getY() == coordinate2.getY()) {
stackList.pop();
a[coordinate2.getX()][coordinate2.getY()] =0;
}
}
}
六 . 结果分析
如下是一个骨灰级别的数独
0,0,0, 0,0,6, 0,0,0
0,3,6, 8,0,2, 0,9,0
0,0,0, 9,0,0, 0,5,0
9,2,0, 0,0,0, 8,6,0
0,0,0, 0,0,0, 0,0,0
0,1,8, 0,0,0, 0,3,7
0,4,0, 0,0,5, 0,0,0
0,8,0, 7,0,9, 6,2,0
0,0,0, 6,0,0, 0,0,0
代码执行一遍，用时81毫秒。
195 476 283
436 852 791
872 931 456
923 517 864
764 398 512
518 264 937
649 125 378
381 749 625
257 683 149
时间：81ms
纸上得来终觉浅，绝知此事要躬行
项目地址 https://gitee.com/YiHaiFeng/ShuDu.git
注 这里只求了一个解。
网友评论