數(shù)獨算法
一 知識背景
無
二 緒言
? ? ? ? 偶爾玩下休閑益智小游戲板乙，一方面可以舒解下心情笙以，另一方面刺激下大腦皮層。百度了一下數(shù)獨 的起源和概念缩搅。說了那么多越败，看著就累。精簡一下就是數(shù)字（0-9）填充游戲硼瓣。不明白的來一張大圖究飞。看到了吧巨双，就這樣子滴~噪猾，先有個直觀印象吧霉祸。
三 規(guī)則
? ? ? ?往簡單點說就3條：
? ? ? ?1.每個橫列需要1~9數(shù)值填充筑累，不能重復(fù)。
? ? ? ?2.每個縱列需要1~9數(shù)值填充丝蹭，不能重復(fù)慢宗。
? ? ? ?3.每個小的九方格里面需要1~9數(shù)值填充，不能重復(fù)奔穿。
四 算法分析
? ? ? ? 首先要寫出這個算法贱田，需要清楚里面的規(guī)則缅茉。數(shù)值可以用9*9的坐標(biāo)來表示，x,y坐標(biāo)在編程語言里面可以用對象男摧，數(shù)組等來表示蔬墩。我在這里選用的數(shù)據(jù)結(jié)構(gòu)有數(shù)組译打，棧。將算法分解一下拇颅，可以得到如下幾塊：
1.用數(shù)組[0][0],[8][8]來表示大的九宮格奏司，空白區(qū)域代表數(shù)值0。
2 小九宮格與九個坐標(biāo)的關(guān)系3n~3n+2樟插，橫縱都是如此韵洋。
_0_0 （n=0）代表第一個 ，里面有九個坐標(biāo)：
? ? ? ? ?（0,0）（0,1）（0,2）
? ? ? ? ?（1,0）（1,1）（1,2）
? ? ? ? ?（2,0）（2,1）（2黄锤，2）
_0_1 (n=1)代表第二個 搪缨，里面有九個小坐標(biāo)
? ? ? ?（0,3）（0,4）（0,5）
? ? ? （1,3）（1,4）（1,5）
? ? ?（2,3）（2,4）（2，5）
? ? ? ? ? ? ? ? ? ? ? 猜扮。
? ? ? ? ? ? ? ? ? ? ? 勉吻。
? ? ? ? ? ? ? ? ? ? ? 。
? ? ? ? ? ? ? 其他類推.
3.規(guī)則
????????橫旅赢，縱齿桃，小方格，數(shù)值1~9值都填滿煮盼，不重復(fù)短纵。
4.判斷算法執(zhí)行完成
數(shù)組里面的值加起來為 9*（1+2+3+4+5+6+7+8+9） = 405 即可。
5. 根據(jù)3規(guī)則得到每個空點（也就是數(shù)值為0的）坐標(biāo)有幾個僵控，然后依次遞歸調(diào)用香到，直到使數(shù)組最后的值為405退出。
五.部分代碼參考
//橫縱坐標(biāo)校驗規(guī)則
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++) {//橫坐標(biāo)校驗
????????????if(a[x][i] == result) {
? ? ? ? ? ? ? ? ? return false;
????????????}
????????}
????????for(inti =0;i <9;i++) {//縱坐標(biāo)校驗
????????????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;
}
//得到一個有效的坐標(biāo)點报破， 1.若果小九宮格已經(jīng)有八個了悠就，返回第九個坐標(biāo)點，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;//執(zhí)行到這說明數(shù)值已經(jīng)填充完了
}
//遞歸調(diào)用充易，找到相應(yīng)的值進(jìn)行填充梗脾，用棧來保存每一步，就和迷宮問題（數(shù)據(jù)結(jié)構(gòu)一種案例）一樣
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)) { ?//執(zhí)行完成
????????????????????????????return;
????????????????????????}
????????????????????Coordinate peek =null;
????????????????????peek = (Coordinate) stackList.peek();
? ? ? ? ? ? ? ? ? ? if(peek.getX() != coordinate.getX() || peek.getY() != coordinate.getY()) {//沒有就填充進(jìn)去
????????????????????????????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;
????????????}
? ? ? ?}
}
六 . 結(jié)果分析
如下是一個骨灰級別的數(shù)獨
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
代碼執(zhí)行一遍盹靴，用時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
注 這里只求了一個解稿静。
