数独英文为sudoku，是一种在9*9 大小方格内，填充1-9 的游戏，要求每行每列，和9 个3*3 的方格内不允许有重复的数字。前几天写了一个解数独的程序：http://blog.foool.net/sudoku/ ‘set value’将方格中数字顺序填入方格内（0 代表该空格未填数字），‘compute’进行计算，规定时间内完成计算则会返回结果。右边有一个计算范例，测试过独数之道中大师级PK 题，可解。
解题有几个思路：
- 每行每列和方格中1-9 中任意数字只能出现一次，当在任何位置出现数字x ，就可以排除所在行、列以及方格中出现该数字x 的可能性
- 当某个数字x 只出现在每行、每列或者每个格子中一次，那么这个位置一定是数字x ，因为如果不是该数字x ，就不满足每行每列、每个方格都出现一次。
- 1,2 步骤每进行一次都会减小未确定方格可能数字的集合，当集合只有一个元素时，则确定该位置的值。
使用的是XAMPP+python+WSGI_MOD+WEB.PY 做的。
1: import copy
2:
3: sudoku_map = [\
4: 0,0,7,4,0,0,0,5,0,\
5: 0,0,4,0,2,9,0,0,7,\
6: 2,9,0,0,0,6,0,0,0,\
7: 0,0,2,0,0,0,0,0,5,\
8: 8,0,0,0,0,0,4,0,0,\
9: 4,0,9,6,5,0,1,0,8,\
10: 0,0,0,0,0,3,0,8,4,\
11: 5,0,0,1,0,7,3,0,0,\
12: 0,4,0,0,8,0,7,0,0]
13:
14: sudoku_nums = {}
15: sudoku_nums_backup = {}
16:
17: for i in xrange(0,81):
18: if sudoku_map[i]==0:
19: sudoku_nums[i] = [1,2,3,4,5,6,7,8,9]
20: else:
21: sudoku_nums[i] = [sudoku_map[i]]
22:
23: grid_index = [\
24: [0,1,2,9,10,11,18,19,20],\
25: [3,4,5,12,13,14,21,22,23],\
26: [6,7,8,15,16,17,24,25,26],\
27: [27,28,29,36,37,38,45,46,47],\
28: [30,31,32,39,40,41,48,49,50],\
29: [33,34,35,42,43,44,51,52,53],\
30: [54,55,56,63,64,65,72,73,74],\
31: [57,58,59,66,67,68,75,76,77],\
32: [60,61,62,69,70,71,78,79,80]]
33:
34:
35:
36: def row_reduction(sudoku_map,i):
37: global sudoku_nums;
38: for j in xrange(0,9):
39: index = i*9 + j
40: value = sudoku_map[index]
41: if value == 0:
42: pass
43: else:
44: for k in xrange(0,9):
45: cur = i*9 + k
46: if cur == index:
47: pass
48: else:
49: if value in sudoku_nums[cur]:
50: sudoku_nums[cur].remove(value)
51: else:
52: pass
53: return sudoku_map
54:
55: def col_reduction(sudoku_map,i):
56: global sudoku_nums;
57: for j in xrange(0,9):
58: index = i + j*9
59: value = sudoku_map[index]
60: if value == 0:
61: pass
62: else:
63: for k in xrange(0,9):
64: cur = i + k*9
65: if cur == index:
66: pass
67: else:
68: if value in sudoku_nums[cur]:
69: sudoku_nums[cur].remove(value)
70: else:
71: pass
72: return sudoku_map
73:
74:
75:
76: def grid_reduction(sudoku_map,i):
77: global sudoku_nums;
78: for j in xrange(0,9):
79: index = grid_index[i][j]
80: value = sudoku_map[index]
81: if value == 0:
82: pass
83: else:
84: for k in xrange(0,9):
85: cur = grid_index[i][k]
86: if cur == index:
87: pass
88: else:
89: if value in sudoku_nums[cur]:
90: sudoku_nums[cur].remove(value)
91: else:
92: pass
93: return sudoku_map
94:
95: def single_in_row_col_grid(sudoku_map,i,value):
96: row = i/9
97: col = i%9
98: grid = (row/3)*3 + col/3
99:
100: '''check row'''
101: for j in xrange(0,9):
102: if j == col:
103: continue
104: else:
105: if value in sudoku_nums[row*9+j]:
106: break
107: if j == 8:
108: return 1
109:
110: '''check column'''
111: for j in xrange(0,9):
112: if j == row:
113: continue
114: else:
115: if value in sudoku_nums[j*9+col]:
116: break
117: if j == 8:
118: return 1
119:
120: '''check grid'''
121: for j in xrange(0,9):
122: cur = grid_index[grid][j]
123: if cur == i:
124: continue
125: else:
126: if value in sudoku_nums[cur]:
127: break
128: if j == 8:
129: return 1
130: return 0
131:
132: def sudoku_map_reduction(sudoku_map):
133: global sudoku_nums
134: for i in xrange(0,81):
135: if len(sudoku_nums[i]) == 1:
136: '''this position has only choice'''
137: sudoku_map[i] = sudoku_nums[i][0]
138: if len(sudoku_nums[i]) == 0:
139: sudoku_map[i] = 0;
140: else:
141: for value in sudoku_nums[i]:
142: '''this is the only choice in row
143: or column or grid of the position'''
144: if single_in_row_col_grid(sudoku_map,i,value) == 1:
145: sudoku_map[i] = value
146: sudoku_nums[i] = [value]
147: return sudoku_map
148:
149: def looper(sudoku_map):
150: for i in xrange(0,9):
151: row_reduction(sudoku_map,i)
152: col_reduction(sudoku_map,i)
153: grid_reduction(sudoku_map,i)
154:
155: sudoku_map = sudoku_map_reduction(sudoku_map)
156: return sudoku_map
157:
158: def pprint(lst):
159: for i in xrange(0,9):
160: print lst[i*9:i*9+9]
161:
162: def can_do(i,value):
163: global sudoku_map
164: global sudoku_nums
165: global sudoku_nums_backup
166:
167: sudoku_map_tmp = copy.deepcopy(sudoku_map)
168: sudoku_nums_tmp = copy.deepcopy(sudoku_nums)
169: sudoku_nums_backup_tmp = copy.deepcopy(sudoku_nums_backup)
170:
171: sudoku_map[i] = value
172: sudoku_nums[i] = [value]
173:
174: for i in xrange(0,7):
175: sudoku_nums_backup = copy.deepcopy(sudoku_nums)
176: sudoku_map = looper(sudoku_map)
177: if 0 not in sudoku_map:
178: return 1
179: else:
180: continue
181: sudoku_map = copy.deepcopy(sudoku_map_tmp)
182: sudoku_nums = copy.deepcopy(sudoku_nums_tmp)
183: sudoku_nums_backup = copy.deepcopy(sudoku_nums_backup_tmp)
184: return 0
185:
186:
187:
188: def hard_try():
189: for i in xrange(0,81):
190: for value in sudoku_nums[i]:
191: if can_do(i,value) == 1:
192: print "find it"
193: pprint(sudoku_map)
194: return
195: else:
196: pass
197: print "no solution"
198:
199: def main():
200: global sudoku_map
201: global sudoku_nums
202: global sudoku_nums_backup
203: while 1:
204: print "++++++"
205: if cmp(sudoku_nums, sudoku_nums_backup) == 0:
206: sudoku_nums_backup = sudoku_nums
207: pprint(sudoku_map)
208: if 0 in sudoku_map:
209: hard_try()
210: exit()
211: else:
212: print "easy solution"
213: exit()
214: else:
215: sudoku_nums_backup = copy.deepcopy(sudoku_nums)
216: sudoku_map = looper(sudoku_map)
217:
218: if "__main__"==__name__:
219: main()
嗯，好，赞一个！没进来之前，我还猜测是用PHP做的呢！
如果能用PHP JS Python 比较下速度应该不错的