程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> C語言求解數獨

C語言求解數獨

編輯:關於C

平時喜歡玩數獨游戲,昨日突發想用程序自動求解。思路是回溯法,不斷試探。

程序代碼如下:


  1 #include<stdio.h>
  2
  3 /*
  4 {0,0,4,6,0,2,0,9,1},
  5 {2,1,0,9,8,4,0,5,6},
  6 {9,0,0,0,7,1,4,2,0},
  7 {1,2,5,0,6,0,3,4,7},
  8 {4,7,6,0,0,0,9,8,5},
  9 {8,3,9,0,4,0,1,6,2},
 10 {0,9,1,2,5,0,0,0,4},
 11 {5,8,0,4,1,6,0,3,9},
 12 {6,4,0,3,0,7,5,0,0}};
 13 */
 14
 15 int data[9][9] = {
 16 {0,7,0,2,6,0,9,0,0},
 17 {3,0,0,0,0,8,0,0,7},
 18 {0,9,0,0,5,7,0,0,0},
 19 {5,0,0,0,0,0,0,7,0},
 20 {0,4,7,3,1,2,8,5,0},
 21 {0,8,0,0,0,0,0,0,1},
 22 {0,0,0,8,2,0,0,4,0},
 23 {7,0,0,6,0,0,0,0,2},
 24 {0,0,4,0,3,9,0,8,0}};
 25
 26 void input()
 27 {
 28     int i,j;
 29     for(i = 0;i < 9;i++)
 30         for(j = 0;j < 9;j++)
 31             scanf("%d",&data[i][j]);
 32 }
 33
 34 void output()
 35 {
 36     int i,j;
 37     for(i = 0;i < 9;i++)
 38     {
 39         for(j = 0;j < 9;j++)
 40             printf("%d ",data[i][j]);
 41         printf("\n");
 42     }
 43     printf("\n");
 44 }
 45
 46 /*檢查num是否可放置在3*3區域是否有沖突*/
 47 int CheckSquare(int line,int col,int num)
 48 {
 49     int i = (line / 3) * 3;
 50     int j = (col / 3) * 3;
 51     int m,n;
 52     for(m = i;m < i + 3;m++)
 53         for(n = j;n < j + 3;n++)
 54             if((data[m][n] == num) && !(m == line && n == col))
 55                 return 0;
 56     return 1;
 57 }
 58
 59 /*檢查行沖突*/
 60 int CheckLine(int line,int col,int num)
 61 {
 62     int i = 9;
 63     while(i--)
 64         if((data[line][i] == num) && (i != col))
 65             return 0;
 66     return 1;
 67 }
 68
 69 /*檢查列沖突*/
 70 int CheckColumn(int line,int col,int num)
 71 {
 72     int i = 9;
 73     while(i--)
 74         if((data[i][col] == num) && (i != line))
 75             return 0;
 76     return 1;
 77 }
 78
 79 /*檢查i行j列是否可放置num*/
 80 int Check(int i,int j,int num)
 81 {
 82     return CheckSquare(i,j,num) && CheckLine(i,j,num) && CheckColumn(i,j,num);
 83 }
 84
 85 /*檢查是否完成*/
 86 int IsDone()
 87 {
 88     int i,j;
 89     for(i = 0;i < 9;i++)
 90         for(j = 0;j < 9;j++)
 91             if(!Check(i,j,data[i][j]) || (data[i][j] == 0))
 92                 return 0;
 93     return 1;
 94 }
 95
 96 void Calc()
 97 {
 98     int i,j,x;
 99     if(IsDone())
100     {
101         output();
102         return;
103     }
104     for(i = 0;i < 9;i++)
105     {
106         for(j = 0;j < 9;j++)
107         {
108             if(data[i][j] == 0)
109             {
110                 for(x = 1; x <= 9;x++)
111                 {
112                     if(Check(i,j,x))
113                     {
114                         data[i][j] = x;
115                         Calc();
116                     }
117                 }
118                 if(x == 10)
119                 {
120                     data[i][j] = 0;
121                     return ;
122                 }
123             }
124         }
125     }
126 }
127
128 int main()
129 {
130 //    input();
131     Calc();
132     output();
133
134     return 0;
135 }
上述程序中,數字0表示該位置為空,待填入數字。

 

 

摘自 泡泡騰

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved