题目96：开发一种解决数独问题的算法

欧拉计划

Su Doku

Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.

A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.

The 6K text file, sudoku.txt (right click and 'Save Link/Target As...'), contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).

By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.

题目：

数独（日文意思是数字的位置）是一种流行的解谜游戏。其起源不详，但是 Leonhard Euler 的功劳不可不提，他发明了一种类似的但是更难的游戏叫做拉丁方块。数独游戏的目的是将一个 9×9 的网格中空白的（或者为 0 的）格子填上适当的数字，使得网格中每一行，每一列以及每个 3×3 的格子中都包含 1 到 9 中的每个数字。以下为一个数独游戏的初始状态及其解。

一个构造良好的数独游戏有且只有一个解并可通过逻辑推理得到，虽然有时需要使用“猜测加证实”的方法来减少可能性（该意见目前让具有很大争议）。搜索的复杂性决定了游戏的难度；以上例子是一个简单的数独游戏，因为其解可以通过直接推理得到。

p096_sudoku.txt (4.78 KB, 下载次数: 26)

2016-8-11 23:29 上传

点击文件名下载附件

包含 50 个难度不同的数独游戏且每个都具有唯一解，其中第一个就是上面的例子。

将 50 个数独游戏全部解出，并求每个解出的网格左上角的三位数之和；例如，上面例子中网格左上角的三位数是 483。

jerryxjr1220

数独算法：

1. class point:  
   
2.     def __init__(self,x,y):  
   
3.         self.x=x  
   
4.         self.y=y  
   
5.         self.available=[]  
   
6.         self.value=0  
   
7.   
   
8. def rowNum(p,sudoku):  
   
9.     row=set(sudoku[p.y*9:(p.y+1)*9])  
   
10.     row.remove(0)  
    
11.     return row #set type  
    
12.   
    
13. def colNum(p,sudoku):  
    
14.     col=[]  
    
15.     length=len(sudoku)  
    
16.     for i in range(p.x,length,9):  
    
17.         col.append(sudoku[i])  
    
18.     col=set(col)  
    
19.     col.remove(0)  
    
20.     return col #set type  
    
21.   
    
22. def blockNum(p,sudoku):  
    
23.     block_x=p.x//3  
    
24.     block_y=p.y//3  
    
25.     block=[]  
    
26.     start=block_y*3*9+block_x*3  
    
27.     for i in range(start,start+3):  
    
28.         block.append(sudoku[i])  
    
29.     for i in range(start+9,start+9+3):  
    
30.         block.append(sudoku[i])  
    
31.     for i in range(start+9+9,start+9+9+3):  
    
32.         block.append(sudoku[i])  
    
33.     block=set(block)  
    
34.     block.remove(0)  
    
35.     return block #set type  
    
36.   
    
37. def initPoint(sudoku):  
    
38.     pointList=[]  
    
39.     length=len(sudoku)  
    
40.     for i in range(length):  
    
41.         if sudoku[i]==0:  
    
42.             p=point(i%9,i//9)  
    
43.             for j in range(1,10):  
    
44.                 if j not in rowNum(p,sudoku) and j not in colNum(p,sudoku) and j not in blockNum(p,sudoku):  
    
45.                     p.available.append(j)  
    
46.             pointList.append(p)  
    
47.     return pointList  
    
48.   
    
49.   
    
50. def tryInsert(p,sudoku):  
    
51.     availNum=p.available  
    
52.     for v in availNum:  
    
53.         p.value=v  
    
54.         if check(p,sudoku):  
    
55.             sudoku[p.y*9+p.x]=p.value  
    
56.             if len(pointList)<=0:  
    
57.                 showSudoku(sudoku)
    
58.                 exit()  
    
59.             p2=pointList.pop()
    
60.             tryInsert(p2,sudoku)
    
61.             sudoku[p2.y*9+p2.x]=0  
    
62.             sudoku[p.y*9+p.x]=0  
    
63.             p2.value=0  
    
64.             pointList.append(p2)  
    
65.         else:  
    
66.             pass      
    
67.   
    
68. def check(p,sudoku):  
    
69.     if p.value==0:  
    
70.         print('not assign value to point p!!')  
    
71.         return False  
    
72.     if p.value not in rowNum(p,sudoku) and p.value not in colNum(p,sudoku) and p.value not in blockNum(p,sudoku):  
    
73.         return True  
    
74.     else:  
    
75.         return False  
    
76.   
    
77. def showSudoku(sudoku):  
    
78.     for j in range(9):  
    
79.         for i in range(9):  
    
80.             print('%d '%(sudoku[j*9+i]),end='')  
    
81.         print('')     
    
82.   
    
83. if __name__=='__main__':  
    
84.     sudoku=[3,0,0,2,0,0,0,0,0,0,0,0,1,0,7,0,0,0,7,0,6,0,3,0,5,0,0,0,7,0,0,0,9,0,8,0,9,0,0,0,2,0,0,0,4,0,1,0,8,0,0,0,5,0,0,0,9,0,4,0,3,0,1,0,0,0,7,0,2,0,0,0,0,0,0,0,0,8,0,0,6]  
    
85.     pointList=initPoint(sudoku)  
    
86.     showSudoku(sudoku)  
    
87.     print('\n')  
    
88.     p=pointList.pop()  
    
89.     tryInsert(p,sudoku)

复制代码

jerryxjr1220

结果： 24702

gunjang

事先声明，网上的算法，采用Exact cover算法
妖风阵阵，完全看不懂。。。
例子就是那个有名针对暴力回溯法采取的解
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[2, 4, 6, 1, 7, 3, 9, 8, 5]
[3, 5, 1, 9, 2, 8, 7, 4, 6]
[1, 2, 8, 5, 3, 7, 6, 9, 4]
[6, 3, 4, 8, 9, 2, 1, 5, 7]
[7, 9, 5, 4, 6, 1, 8, 3, 2]
[5, 1, 9, 2, 8, 6, 4, 7, 3]
[4, 7, 2, 3, 1, 9, 5, 6, 8]
[8, 6, 3, 7, 4, 5, 2, 1, 9]
欢迎大神给出注释

1. #!/usr/bin/env python3
   
2. 
   
3. # Author: Ali Assaf <ali.assaf.mail@gmail.com>
   
4. # Copyright: (C) 2010 Ali Assaf
   
5. # License: GNU General Public License <http://www.gnu.org/licenses/>
   
6. 
   
7. from itertools import product
   
8. 
   
9. def solve_sudoku(size, grid):
   
10.     R, C = size
    
11.     N = R * C
    
12.     X = ([("rc", rc) for rc in product(range(N), range(N))] +
    
13.          [("rn", rn) for rn in product(range(N), range(1, N + 1))] +
    
14.          [("cn", cn) for cn in product(range(N), range(1, N + 1))] +
    
15.          [("bn", bn) for bn in product(range(N), range(1, N + 1))])
    
16.     Y = dict()
    
17.     for r, c, n in product(range(N), range(N), range(1, N + 1)):
    
18.         b = (r // R) * R + (c // C) # Box number
    
19.         Y[(r, c, n)] = [
    
20.             ("rc", (r, c)),
    
21.             ("rn", (r, n)),
    
22.             ("cn", (c, n)),
    
23.             ("bn", (b, n))]
    
24.     X, Y = exact_cover(X, Y)
    
25.     for i, row in enumerate(grid):
    
26.         for j, n in enumerate(row):
    
27.             if n:
    
28.                 select(X, Y, (i, j, n))
    
29.     for solution in solve(X, Y, []):
    
30.         for (r, c, n) in solution:
    
31.             grid[r][c] = n
    
32.         yield grid
    
33. 
    
34. def exact_cover(X, Y):
    
35.     X = {j: set() for j in X}
    
36.     for i, row in Y.items():
    
37.         for j in row:
    
38.             X[j].add(i)
    
39.     return X, Y
    
40. 
    
41. def solve(X, Y, solution):
    
42.     if not X:
    
43.         yield list(solution)
    
44.     else:
    
45.         c = min(X, key=lambda c: len(X[c]))
    
46.         for r in list(X[c]):
    
47.             solution.append(r)
    
48.             cols = select(X, Y, r)
    
49.             for s in solve(X, Y, solution):
    
50.                 yield s
    
51.             deselect(X, Y, r, cols)
    
52.             solution.pop()
    
53. 
    
54. def select(X, Y, r):
    
55.     cols = []
    
56.     for j in Y[r]:
    
57.         for i in X[j]:
    
58.             for k in Y[i]:
    
59.                 if k != j:
    
60.                     X[k].remove(i)
    
61.         cols.append(X.pop(j))
    
62.     return cols
    
63. 
    
64. def deselect(X, Y, r, cols):
    
65.     for j in reversed(Y[r]):
    
66.         X[j] = cols.pop()
    
67.         for i in X[j]:
    
68.             for k in Y[i]:
    
69.                 if k != j:
    
70.                     X[k].add(i)
    
71. 
    
72. if __name__ == "__main__":
    
73.     #A Sudoku designed to work against the brute force algorithm. in wikipedia
    
74.     grid = [
    
75.     [0,0,0,0,0,0,0,0,0],
    
76.     [0,0,0,0,0,3,0,8,5],
    
77.     [0,0,1,0,2,0,0,0,0],
    
78.     [0,0,0,5,0,7,0,0,0],
    
79.     [0,0,4,0,0,0,1,0,0],
    
80.     [0,9,0,0,0,0,0,0,0],
    
81.     [5,0,0,0,0,0,0,7,3],
    
82.     [0,0,2,0,1,0,0,0,0],
    
83.     [0,0,0,0,4,0,0,0,9]]
    
84.     for solution in solve_sudoku((3, 3), grid):
    
85.          print(*solution, sep='\n')

复制代码

jerryxjr1220

gunjang 发表于 2017-8-26 21:28
事先声明，网上的算法，采用Exact cover算法
妖风阵阵，完全看不懂。。。
例子就是那个有名针对暴力回溯 ...

给你看个更牛的第三方库来求解数独问题。
同样求解你的例题，0.3s出答案。

1. g = [
   
2. [0,0,0,0,0,0,0,0,0],
   
3. [0,0,0,0,0,3,0,8,5],
   
4. [0,0,1,0,2,0,0,0,0],
   
5. [0,0,0,5,0,7,0,0,0],
   
6. [0,0,4,0,0,0,1,0,0],
   
7. [0,9,0,0,0,0,0,0,0],
   
8. [5,0,0,0,0,0,0,7,3],
   
9. [0,0,2,0,1,0,0,0,0],
   
10. [0,0,0,0,4,0,0,0,9]]
    
11. 
    
12. from pymprog import model, iprod
    
13. p = model("sudoku")
    
14. I = range(1,10)
    
15. J = range(1,10)
    
16. K = range(1,10)
    
17. T = iprod(I,J,K) #create Indice tuples
    
18. x = p.var('x', T, bool)
    
19. #x[i,j,k] = 1 means cell [i,j] is assigned number k
    
20. #assign pre-defined numbers using the "givens"
    
21. [x[i,j,k] == (1 if g[i-1][j-1] == k else 0)
    
22.        for (i,j,k) in T if g[i-1][j-1] > 0 ]
    
23. 
    
24. #each cell must be assigned exactly one number
    
25. [sum(x[i,j,k] for k in K)==1 for i in I for j in J]
    
26. 
    
27. #cells in the same row must be assigned distinct numbers
    
28. [sum(x[i,j,k] for j in J)==1 for i in I for k in K]
    
29. 
    
30. #cells in the same column must be assigned distinct numbers
    
31. [sum(x[i,j,k] for i in I)==1 for j in J for k in K]
    
32. 
    
33. #cells in the same region must be assigned distinct numbers
    
34. [sum(x[i,j,k] for i in range(r,r+3) for j in range(c, c+3))==1
    
35.     for r in range(1,10,3) for c in range(1,10,3) for k in K]
    
36.    
    
37. #there is no need for an objective function here
    
38. 
    
39. p.solve()
    
40. 
    
41. for i in I:
    
42.    if i in range(1,10,3):
    
43.       print(" +-------+-------+-------+")
    
44.    print('', end=' ')
    
45.    for j in J:
    
46.       if j in range(1,10,3): print("|", end=' ')
    
47.       print("%g"%sum(x[i,j,k].primal*k for k in K), end=' ')
    
48.       if j==9: print("|")
    
49.    if i == 9:
    
50.       print(" +-------+-------+-------+")
    
51. p.end()

复制代码

有空我会详细介绍这个超牛逼的第三方库，可以解决很多普通方法无法解决的线性规划问题。
先卖个关子

guosl

1. /*
   
2. 本题用深度搜索，结果秒出
   
3. 结果：24702
   
4. */
   
5. #include <cstdio>
   
6. #include <cstdlib>
   
7. #include <cstring>
   
8. 
   
9. char r[9][10], c[9][10], b[3][3][10];
   
10. int a[9][9];
    
11. int nSum = 0;
    
12. 
    
13. void dfs(int k)
    
14. {
    
15.   if (k == 81)//已经填好了
    
16.   {
    
17.     char str[4];
    
18.     str[0] = a[0][0] + '0';
    
19.     str[1] = a[0][1] + '0';
    
20.     str[2] = a[0][2] + '0';
    
21.     str[3] = 0;
    
22.     nSum += atoi(str);//统计结果
    
23.     return;
    
24.   }
    
25.   int nr = k / 9;//计算出当前的行和列
    
26.   int nc = k % 9;
    
27.   if (a[nr][nc] != 0)//这个格子已经有数字跳过
    
28.   {
    
29.     dfs(k + 1);
    
30.     return;
    
31.   }
    
32.   int nbr = nr / 3;//计算出所在块的位置
    
33.   int nbc = nc / 3;
    
34.   for (int i = 1; i <= 9; ++i)//试填数字
    
35.   {
    
36.     if (r[nr][i] == 0 && c[nc][i] == 0 && b[nbr][nbc][i] == 0)//检查这个数字是否已经被用过了
    
37.     {
    
38.       //在这个格子填
    
39.       r[nr][i] = 1;
    
40.       c[nc][i] = 1;
    
41.       b[nbr][nbc][i] = 1;
    
42.       a[nr][nc] = i;
    
43.       dfs(k + 1);//继续深入填下一个格子
    
44.       //回溯
    
45.       a[nr][nc] = 0;
    
46.       r[nr][i] = 0;
    
47.       c[nc][i] = 0;
    
48.       b[nbr][nbc][i] = 0;
    
49.     }
    
50.   }
    
51. }
    
52. 
    
53. int main(void)
    
54. {
    
55.   errno_t err;
    
56.   FILE *fp = NULL;
    
57.   err = fopen_s(&fp, "p096_sudoku.txt", "r");//打开文件
    
58.   if (err != 0)
    
59.   {
    
60.     printf_s("数据文件未打开\n");
    
61.     return 0;
    
62.   }
    
63.   char str[256];
    
64.   while (fgets(str, 255, fp) != NULL)//读数据
    
65.   {
    
66.     //初始化变量
    
67.     memset(r, 0, sizeof(r));
    
68.     memset(c, 0, sizeof(c));
    
69.     memset(b, 0, sizeof(b));
    
70.     for (int i = 0; i < 9; ++i)
    
71.     {
    
72.       fgets(str, 255, fp);//读入当前行的数据
    
73.       for (int j = 0; j < 9; ++j)
    
74.       {
    
75.         //填充各个格子的数据
    
76.         a[i][j] = int(str[j]) - 48;
    
77.         r[i][a[i][j]] = 1;
    
78.         c[j][a[i][j]] = 1;
    
79.         b[i / 3][j / 3][a[i][j]] = 1;
    
80.       }
    
81.     }
    
82.     dfs(0);//开始探索
    
83.   }
    
84.   fclose(fp);
    
85.   printf_s("%d\n", nSum);
    
86.   return 0;
    
87. }

复制代码