1 #!/usr/bin/env python
  2 # encoding: utf-8
  3 
  4 """
  5 @version: 暴力破解
  6 @author: Wish Chen
  7 @contact: 986859110@qq.com
  8 @file: solving_sodoku.py
  9 @time: 2018/11/27 5:23
 10 
 11 """
 12 import time
 13 history = {}
 14 search_history = []
 15 start_time = 0
 16 
 17 
 18 def show_sudoku(l):
 19     """
 20     print a sudoku
 21     格式化输出
 22     :param sudoku:
 23     :return:
 24     """
 25     global start_time
 26     for i in range(9):
 27         for j in range(9):
 28             print(l[i*9+j], end='')
 29             if j% 3 == 2:
 30                 print('|', end='')
 31             else:
 32                 print(' ', end='')
 33         if i % 3 == 2 and i < 8:
 34             print('\n------------------', end='')
 35         print('')
 36     print('\n\n')
 37     print('用时%.3fs' % (time.time() - start_time))
 38 
 39 
 40 def read_from_file():
 41     """
 42     read a sudoku from '1.in'
 43     :return:
 44     """
 45     l = []
 46     with open('5.in', 'r') as f:
 47         for i in range(9):
 48             row = f.readline().strip().split(' ')
 49             for j in row:
 50                 l.append(int(j))
 51     return l
 52 
 53 
 54 def initialize():
 55     """
 56     初始化历史搜索列表
 57     :return:
 58     """
 59     for i in range(81):
 60         history[i] = []
 61 
 62 
 63 def num_list(index, l):
 64     """
 65     计算出index的位置能有哪些数
 66     :param index:
 67     :param l:
 68     :return:
 69     """
 70     global history
 71     i = index // 9
 72     j = index % 9
 73     list_b = [False, False, False, False, False, False, False, False, False]  # 可以填的数为False, 接下来开始排除
 74     for k in range(9):
 75         if l[i*9+k] != 0: list_b[l[i*9+k]-1] = True  # 排除同行
 76         if l[k*9+j] != 0: list_b[l[k*9+j]-1] = True  # 排除同列
 77 
 78     ii = i // 3 * 3
 79     jj = j // 3 * 3
 80     for row in range(ii, ii+3):
 81         for col in range(jj, jj+3):
 82             if l[row*9+col] != 0: list_b[l[row*9+col]-1] = True  # 排除九宫格
 83 
 84     for num in history[index]:
 85         list_b[num-1] = True  # 排除已搜索过的
 86 
 87     list_n = []
 88     for i in range(len(list_b)):
 89         if not list_b[i]: list_n.append(i+1)
 90     return list_n
 91 
 92 
 93 
 94 
 95 
 96 def solve(l):
 97     """
 98     暴力破解 深搜
 99     :param l:
100     :return:
101     """
102     x = 0
103     n = 0
104     flag = True
105     while flag:
106         while flag and x < 81:
107             n += 1
108             if l[x] == 0:
109                 list_can = num_list(x, l)  # 获取该单元格所有可以被搜索的值
110                 if list_can:  # 该单元格有可以被搜索的值
111                     search_history.append(x)
112                     history[x].append(list_can[0])
113                     l[x] = list_can[0]
114                 else:  # 该单元格没有可以被搜索的值,则说明这条路不通, 回滚
115                     if search_history:  # 有搜索历史, 则回滚
116                         history[x] = []
117                         x = search_history.pop()
118                         l[x] = 0
119                         continue
120                     else:  # 没有搜索历史, 即第一个值所有都不行, 无解
121                         flag = False
122             x += 1
123         if flag:
124             show_sudoku(l)
125             x = search_history.pop()
126             l[x] = 0
127     print(n)
128 
129 
130 if __name__ == '__main__':
131     sudoku = read_from_file()
132     show_sudoku(sudoku)
133     start_time = time.time()
134     initialize()
135     solve(sudoku)
136     print('总用时%.3fs' % (time.time() - start_time))

  1 #!/usr/bin/env python
  2 # encoding: utf-8
  3 
  4 """
  5 @version: 先利用唯一候选数法和隐性唯一候选数法优化后暴力破解
  6 @author: Wish Chen
  7 @contact: 986859110@qq.com
  8 @file: solving_sodoku.py
  9 @time: 2018/11/27 5:23
 10 
 11 """
 12 import time, copy
 13 
 14 V = [1, 2, 4, 8, 16, 32, 64, 128, 256, 511]
 15 vn = {1: 1, 2: 2, 4: 3, 8: 4, 16: 5,
 16       32: 6, 64: 7, 128: 8, 256: 9}
 17 history = []
 18 
 19 
 20 def show_sudoku(l, num=1):
 21     """
 22     print a sudoku
 23     格式化输出
 24     :param sudoku:
 25     :return:
 26     """
 27     global start_time
 28     for i in range(9):
 29         for j in range(9):
 30             print(l[i * 9 + j] * num, end='')
 31             if j % 3 == 2:
 32                 print('|', end='')
 33             else:
 34                 print(' ', end='')
 35         if i % 3 == 2 and i < 8:
 36             print('\n------------------', end='')
 37         print('')
 38     print('\n\n')
 39     if num == -1:
 40         print('用时%.3fs' % (time.time() - start_time))
 41 
 42 
 43 def read_from_file():
 44     """
 45     read a sudoku from '1.in'
 46     :return:
 47     """
 48     l = []
 49     with open('1.in', 'r') as f:
 50         for i in range(9):
 51             row = f.readline().strip().split(' ')
 52             for j in row:
 53                 l.append(int(j))
 54     return l
 55 
 56 
 57 def initialize(l):
 58     """
 59     初始化,将所有未填写的部分设置为(111111111)B
 60     遍历整个数独,已填写的数字让其约束生效
 61     :param l:
 62     :return:
 63     """
 64     for i in range(81):
 65         if l[i] == 0:
 66             l[i] = V[9]
 67         else:
 68             l[i] = -l[i]
 69 
 70     for i in range(81):
 71         if l[i] < 0:
 72             put_in(i, -l[i], l)  # 填下一个数字, 使约束生效
 73 
 74 
 75 def choice(index, l):
 76     """
 77     返回序号为index下
 78     所有的可以填入的数字的个数
 79     :param index:
 80     :param l:
 81     :return:
 82     """
 83     x = l[index]
 84     n = 0
 85     while x > 0:
 86         x = x & (x-1)
 87         n += 1
 88     return n
 89 
 90 
 91 def get_first_value(l):
 92     """
 93     返回第一个需要填写的格子
 94     首先检查有没有矛盾
 95     :param l:
 96     :return:
 97     """
 98     for i in range(81):  # 检查有没有矛盾
 99         if l[i] == 0:
100             return i
101 
102     x = 0
103     while l[x] < 0:
104         x += 1
105     return x
106 
107 
108 def solve_only_one(l):
109     """
110     唯一候选数法
111     :param l:
112     :return:
113     """
114     flag = True  # 初始化flag, flag表示这一趟循环有没有填入新的数字
115     while flag:
116         flag = False
117         for i in range(81):
118             if choice(i, l) == 1:  # 如果这个格子可以填写的数字只有一个
119                 flag = True
120                 l[i] = -vn[l[i]]
121                 l = put_in(i, -l[i], l)
122     return l
123 
124 
125 def solve_hide_one(l):
126     """
127     隐形唯一候选数法
128     :param l:
129     :return:
130     """
131     flag = True  # 初始化flag, flag表示这一趟循环有没有填入新的数字
132     while flag:  # 不停循环
133         flag = False
134         for n in range(9):
135             for i in range(9):
136                 num = 0
137                 for j in range(9):
138                     if l[i * 9 + j] > 0 and l[i * 9 + j] & V[n] == V[n]:
139                         num += 1
140                         temp = i * 9 + j
141                 if num == 1:
142                     flag = True
143                     l[temp] = - n - 1
144                     l = put_in(temp, n + 1, l)  # 每一行进行隐性唯一候选数法
145 
146                 num = 0
147                 for j in range(9):
148                     if l[j * 9 + i] > 0 and l[j * 9 + i] & V[n] == V[n]:
149                         num += 1
150                         temp = j * 9 + i
151                 if num == 1:
152                     flag = True
153                     l[temp] = - n - 1
154                     l = put_in(temp, n + 1, l)  # 每一列进行隐性唯一候选数法
155 
156             for i in range(3):
157                 for j in range(3):
158                     num = 0
159                     for row in range(3):
160                         for col in range(3):
161                             index = (i * 3 + row) * 9 + j * 3 + col
162                             if l[index] > 0 and l[index] & V[n] == V[n]:
163                                 num += 1
164                                 temp = index
165                     if num == 1:
166                         flag = True
167                         l[temp] = - n - 1
168                         l = put_in(temp, n + 1, l)  # 每一九宫格进行隐性唯一候选数法
169     return l
170 
171 
172 def map_list(l):
173     """
174     深搜
175     首先通过两个数独解法填入简单的数字
176 
177     :param l:
178     :return:
179     """
180     global history
181     l = solve_only_one(l)
182     l = solve_hide_one(l)
183     n = get_first_value(l)
184     if n == 81:
185         show_sudoku(l, -1)
186         return
187     else:
188         if l[n] == 0:
189             return
190         else:
191             i = 8
192             while l[n] < V[i]:
193                 i -= 1
194             l[n] -= V[i]
195             history.append(copy.deepcopy(l))  # 将此时的数独状态放入历史搜索列表
196             l[n] = -(i + 1)
197             l = put_in(n, i+1, l)
198             map_list(l)
199 
200 
201 def put_in(index, n, l):
202     """
203     在index位置插入n
204     制造约束,同行同列同九宫格不再有这个数的选项
205     :param index:
206     :param n:
207     :param l:
208     :return:
209     """
210     x = index // 9
211     y = index % 9
212     for k in range(9):
213         if l[x*9+k] > 0:
214             l[x*9+k] &= V[9] - V[n-1]  # 排除同行
215         if l[k*9+y] > 0:
216             l[k*9+y] &= V[9] - V[n-1]  # 排除同列
217 
218     ii = x // 3 * 3
219     jj = y // 3 * 3
220     for row in range(ii, ii + 3):
221         for col in range(jj, jj + 3):
222             if l[row * 9 + col] > 0:
223                 l[row * 9 + col] &= V[9] - V[n-1]  # 排除九宫格
224 
225     return l
226 
227 
228 if __name__ == '__main__':
229     sudoku = read_from_file()
230     sudoku.append(1)  # 为了方便get_first_value函数, 在末尾设置一个边界
231     show_sudoku(sudoku)
232     start_time = time.time()
233     initialize(sudoku)
234     map_list(sudoku)
235     while history:
236         map_list(history.pop())
237     print('总用时%.3fs' % (time.time() - start_time))