一个数独问题的算法(已更新,提供一个简单算法,欢迎拍砖)
我先把題放出來大家有興趣研究一下。
| ? | ? | 8 | ? | ? | ? | 5 | 7 | 1 |
| 1 | 9 | ? | ? | ? | ? | ? | ? | 2 |
| ? | 6 | ? | 2 | ? | ? | ? | ? | ? |
| ? | 5 | ? | 6 | ? | 9 | ? | ? | ? |
| ? | ? | 2 | 4 | ? | 5 | 8 | ? | ? |
| ? | ? | ? | 8 | ? | 1 | ? | 2 | ? |
| ? | ? | ? | ? | ? | 4 | ? | 9 | ? |
| 4 | ? | ? | ? | ? | ? | 6 | 5 | 7 |
| 5 | 8 | 9 | ? | ? | ? | 1 | ? |
| ? | ? | ? | ? | ? | 5 | ? | ? | 2 |
| ? | ? | 1 | 9 | 6 | ? | ? | ? | 3 |
| ? | 3 | 5 | ? | ? | ? | 7 | 6 | ? |
| ? | ? | 6 | 1 | ? | 4 | ? | 7 | ? |
| ? | 7 | ? | 2 | ? | 6 | ? | 4 | ? |
| ? | 5 | ? | 3 | ? | 8 | 6 | ? | ? |
| ? | 9 | 7 | ? | ? | ? | 8 | 3 | ? |
| 5 | ? | ? | ? | 8 | 3 | 9 | ? | ? |
| 8 | ? | ? | 7 | ? | ? | ? | ? | ? |
| ? | 6 |
|
| 1 | 7 |
|
|
|
|
| 1 | 9 | 3 | 6 |
|
|
|
|
|
|
|
|
|
|
|
|
| 4 |
|
| 5 |
|
|
| 2 |
|
| 8 |
| 8 |
| 1 |
|
|
| 7 |
| 2 |
| 2 |
|
| 7 |
|
|
| 6 |
|
| 6 |
|
|
|
|
|
|
|
|
|
|
|
|
| 7 | 6 | 5 | 3 |
|
|
|
|
| 5 | 4 |
|
| 8 |
|
規則：
在9*9的格子中用1到9填滿格子：
每一行都要用到1~9，位置不限；
每一列都要用到1~9，位置不限；
每3*3格子都要用到1~9，位置不限；
我的算法思想比較簡單：窮舉法，遞歸。
1、初始化：
?新建兩個數組A[9,9],B[9,9],他們的初始值都一樣。
???????? public? static int[,,] A = new int[9,9,9];<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
???????? public? static int[,] B = new int[9,9];
????????????? for(int i=0;i<9;i++)
?????????????????? for(int j=0;j<9;j++)
???????????????????????A[i,j] = 0;
????????????? A[0,1]=6;
????????????? A[0,4]=1;
????????????? A[0,5]=7;
???????????????????………………
????????????? A[8,3]=5;
????????????? A[8,4]=4;
????????????? A[8,7]=8;
????????????? A[8,8]=6;
????????????? for(int m=0;m<9;m++)
?????????????????? for(int n=0;n<9;n++)
?????????????????????? B[m,n] = 0;
????????????? B[0,1]=6;
????????????? B[0,4]=1;
????????????? B[0,5]=7;
???????????????????………………
????????????? B[8,3]=5;
????????????? B[8,4]=4;
????????????? B[8,7]=8;
????????????? B[8,8]=6;
?
遞歸過程：
???????? public void JudgeNumber(int x,int y)
???????? {
????????????? if(x<9&&y<9)?????????????????????????????????//判斷數組下標范圍
????????????? {
?????????????????? if(A[x,y] == 0||A[x,y] != B[x,y])?????? //如果數組的值為零或者取得的值不等于B的值
?????????????????? {
?????????????????????? for(int i=1;i<10;i++)???????????????
?????????????????????? {
??????????????????????????? A[x,y] = i;?????????????????????//循環付值
??????????????????????????? if(Pass(x,y))???????????????????//判斷條件
??????????????????????????? {
???????????????????????????????? if(Victory())??????????????//成功
???????????????????????????????? {
???????????????????????????????????? printShuzu();
???????????????????????????????????? return ;
???????????????????????????????? }
???????????????????????????????? if(y<8)?????????????????????//判斷下一個數
???????????????????????????????????? JudgeNumber(x,y+1);
???????????????????????????????? else
???????????????????????????????????? JudgeNumber(x+1,0);
??????????????????????????? }
?????????????????????? }
?????????????????????? A[x,y] = 0;???????????????????????????//失敗之后把值設為零，以便繼續判斷
?????????????????? }
?????????????????? else??????????????????????????????????????//判斷下一個數
?????????????????? {
?????????????????????? if(y<8)
??????????????????????????? JudgeNumber(x,y+1);
?????????????????????? else
??????????????????????????? JudgeNumber(x+1,0);
?????????????????? }
????????????? }
???????? }
?
???????? public <?xml:namespace prefix = st1 ns = "urn:schemas-microsoft-com:office:smarttags" />boolPass(int i,int j)
???????? {
??????????? //判斷橫豎有無重復
????????????? for(int b=0;b<9;b++)
????????????? {
?????????????????? if(b!=i)
?????????????????????? if(A[i,j] == A[b,j])
??????????????????????????? return false;
?????????????????? if(b!=j)
?????????????????????? if(A[i,j] == A[i,b])
??????????????????????????? return false;
????????????? }
?
??????????? //判斷*3有無重復
????????????? int q0 = (i/3)*3;
????????????? int k0 = (j/3)*3;
????????????? int q1 = (i/3+1)*3;
????????????? int k1 = (j/3+1)*3;
?
????????????? for(int q=q0;q<q1;q++)
?????????????????? for(int k=k0;k<k1;k++)
?????????????????????? if(q!=i&&k!=j)
??????????????????????????? if(A[i,j] == A[q,k])
???????????????????????????????? return false;
????????????? return true;
???????? }
?
??????? /// <summary>
??????? /// 在Pass情況下如果整個數組無0表示成功求解
??????? /// </summary>
??????? /// <returns></returns>
???????? public bool Victory()
???????? {
????????????? bool ax=false;
?????????????
????????????? for(int i=0;i<9;i++)
?????????????????? for(int j=0;j<9;j++)
?????????????????? {
?????????????????????? if(? A[i,j] != 0)
??????????????????????????? ax =true;
?????????????????????? else
??????????????????????????? return false;
?????????????????? }
????????????? return ax;
???????? }
本算法的問題：
1.窮舉取值過多。不必從1~9全部取
2.成功后在遞歸里面不能跳出。
對問題1的改進:
1.新建3維數組A[9,9,9]
2初始判斷,獲取該位置可取值的范圍
????????????? for(int i=0;i<9;i++)
?????????????????? for(int j=0;j<9;j++)
?????????????????? {
?????????????????????? int[] B = new int[9];
?????????????????????? for(int d=0;d<9;d++)
??????????????????????????? B[d] = d+1;
?????????????????????? if(A[i,j,0]==0)
?????????????????????? {
??????????????????????????? for(int a=0;a<9;a++)
??????????????????????????? {
???????????????????????????????? A[i,j,0] = B[a];
???????????????????????????????? for(int b=0;b<9;b++)
???????????????????????????????? {
???????????????????????????????????? if(b!=i)
????????????????????????????????????????? if(A[i,j,0] == A[b,j,0])
?????????????????????????????????????????????? B[a]=0;
???????????????????????????????????? if(b!=j)
????????????????????????????????????????? if(A[i,j,0] == A[i,b,0])
?????????????????????????????????????????????? B[a]=0;
???????????????????????????????? }
???????????????????????????????? int q0 = (i/3)*3;
???????????????????????????????? int k0 = (j/3)*3;
???????????????????????????????? int q1 = (i/3+1)*3;
???????????????????????????????? int k1 = (j/3+1)*3;
?
???????????????????????????????? for(int q=q0;q<q1;q++)
???????????????????????????????????? for(int k=k0;k<k1;k++)
????????????????????????????????????????? if(q!=i&&k!=j)
?????????????????????????????????????????????? if(A[i,j,0] == A[q,k,0])
?????????????????? ???????????????????????????????? B[a]=0;??????
???????????????????????????????? A[i,j,0] = 0;
??????????????????????????? }
?????????????????????? }
?????????????????? }
?3.更改判斷部分.
???????? public void JudgeNumber(int x,int y)
???????? {
????????????? if(x<9&&y<9)
???????? ???? {
?????????????????? if(A[x,y,0] == 0||A[x,y,0] != B[x,y])
?????????????????? {
?????????????????????? for(int i=1;i<9;i++)//更改部分
?????????????????????? {
??????????????????????????? if(A[x,y,i]!=0)//更改部分
??????????????????????????? {
???????????????????????????????? A[x,y,0] = A[x,y,i];//更改部分
???????????????????????????????? if(Pass(x,y))
???????????????????????????????? {
???????????????????????????????????? if(Victory())
???????????????????????????????????? {
????????????????????????????????????????? printShuzu();
????????????????????????????????????????? //return ;
???????????????????????????????????? }
???????????????????????????????????? if(y<8)
????????????????????????????????????????? JudgeNumber(x,y+1);
???????????????????????????????????? else
????????????????????????????????????????? JudgeNumber(x+1,0);
???????????????????????????????? }
??????????????????????????? }
?????????????????????? }
?????????????????????? A[x,y,0] = 0;
?????????????????? }
?????????????????? else
?????????????????? {
?????????????????????? if(y<8)
??????????????????????????? JudgeNumber(x,y+1);
?????????????????????? else
??????????????????????????? JudgeNumber(x+1,0);
?????????????????? }
????????????? }
???????? }
轉載于:https://www.cnblogs.com/wssmax/archive/2006/08/25/486229.html
總結
以上是生活随笔為你收集整理的一个数独问题的算法(已更新,提供一个简单算法,欢迎拍砖)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 3.Cood
- 下一篇： switchhosts使用