数独（shù dú）是源自18世纪瑞士的一种数学游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。
数独盘面是个九宫，每一宫又分为九个小格(cell)。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。 我采用的是枚举的方式去处理数独问题: 即每个格子用1-9这个数字进行测试，判断是否满足两个规则
数独文件存储在easy50.txt中 在代码中会对其进行读取
import copy import time t1=time.time() import os import os def readfile(): a=[] b=[[0]*9]*9 with open('easy50.txt', 'r') as f: for line in f.readlines(): line=line.strip() if '=' not in line: a.append(line) if '=' in line: print(a) xx=input("是否继续:\n") while xx is 'y': a.clear() print("清空",a) break else: return a f.close() li=readfile() arr=[] for i in range(9): for j in range(9): arr.append(int(li[i][j])) a1=[] a2=[] a3=[] a4=[] a5=[] a6=[] a7=[] a8=[] a9=[] for i in range(9): a1.append(arr[i]) for i in range(9,18): a2.append(arr[i]) for i in range(18,27): a3.append(arr[i]) for i in range(27,36): a4.append(arr[i]) for i in range(36,45): a5.append(arr[i]) for i in range(45,54): a6.append(arr[i]) for i in range(54,63): a7.append(arr[i]) for i in range(63,72): a8.append(arr[i]) for i in range(72,81): a9.append(arr[i]) origin = [a1, a2,a3,a4,a5,a6,a7,a8,a9] print("原始origin的值:\n",a1,'\n', a2,'\n',a3,'\n',a4,'\n',a5,'\n',a6,'\n',a7,'\n',a8,'\n',a9) print("--------------------------------------start---------------------------------------") class sudoku: def debug(self): # 调试 for list in origin: print(list) print("\n") def check_repetition(self,list):#判断表中是否有重复值，0除外 flag=0 for i in range(1,10): if list.count(i)>=2: return 1 else: flag=flag+1 if flag==9: return 0 def check_row(self,row):#检测横向是否有重复值，无则为返回0，有则返回1 list = origin[row] # 横向 r1 = self.check_repetition(list) if r1 == 0: return 0 else : return 1 def check_column(self,column):#检测纵向是否重复值，无则为返回0，有则返回1 list = [] # 纵向 for num in origin: list.append(num[column]) r2 = self.check_repetition(list) if r2==0: return 0 else: return 1 def check_square(self,x,y):#检测九宫格是否有重复值，无则为返回0，有则返回1 x,y=y,x if x>=9 or y>=9: return square = []#九宫格 for i in range(0+y//3*3, 3+y//3*3): for j in range(0+x//3*3, 3+x//3*3): square.append(origin[i][j]) r3 = self.check_repetition(square) if r3==0: return 0 else: return 1 def check(self,x,y):#检测是否有重复值，无则为0，有则不为0 r1 = self.check_row(x) r2 = self.check_column(y) r3 = self.check_square(x, y) result=r1+r2+r3 return result def get_next(self): # 获得下一个空值，返回row,column值 i = 0 for list in origin: try: # 当0不在列表中时，跳过 column = list.index(0) row = origin.index(list) res = (row, column) return res except ValueError: i = i + 1 if i == 9: t2=time.time() print("总用时={}".format(t2 - t1)) exit(0) def poi(self,row, column): # 位置修正 if row == 0 and column == -1: return if row == 8 and column == 9: return if column == -1: column = 8 row = row - 1 if column == 9: column = 0 row = row - 1 return (row, column) def get_last(self,row, column): origin[row].insert(column, 0) origin[row].pop(column + 1) column = column - 1 # 获得上一个已填值的行、列位置 row, column = self.poi(row, column)#位置修正 r = origin[row][column] * compare[row][column] while r != 0: column = column - 1 row, column = self.poi(row, column) r = origin[row][column] * compare[row][column] return (row, column) def blank(self): try: row,column=self.get_next() except TypeError:#已填完 exit(0) j=0 flag=0 for i in range(1,10): origin[row].insert(column,i) origin[row].pop(column+1) self.debug() r = self.check(row, column) if r==0:#无重复值 return else: j = j + 1 if j==9: flag=1 break if flag==1: row, column = self.get_last(row, column) value=origin[row][column] self.debug() while value == 9: row, column = self.get_last(row, column) value = origin[row][column] self.debug() while value<9: for k in range(value+1,10): origin[row].insert(column, k) origin[row].pop(column + 1) self.debug() r=self.check(row,column) if r!=0:#有重复 if k==9: row, column = self.get_last(row, column) value=origin[row][column] self.debug() while value==9: row, column = self.get_last(row, column) value = origin[row][column] self.debug() break else: return if __name__=="__main__": compare = copy.deepcopy(origin)#深复制 被复制出来对象对复制出来的对象没有任何影响 sudoku = sudoku()#对象的id值 while 1: sudoku.blank()读取的数独问题文件:
003020600 900305001 001806400 008102900 700000008 006708200 002609500 800203009 005010300 ======== 200080300 060070084 030500209 000105408 000000000 402706000 301007040 720040060 004010003 ======== 000000907 000420180 000705026 100904000 050000040 000507009 920108000 034059000 507000000 ======== 030050040 008010500 460000012 070502080 000603000 040109030 250000098 001020600 080060020 ======== 020810740 700003100 090002805 009040087 400208003 160030200 302700060 005600008 076051090 ======== 100920000 524010000 000000070 050008102 000000000 402700090 060000000 000030945 000071006 ======== 043080250 600000000 000001094 900004070 000608000 010200003 820500000 000000005 034090710 ======== 480006902 002008001 900370060 840010200 003704100 001060049 020085007 700900600 609200018 ======== 000900002 050123400 030000160 908000000 070000090 000000205 091000050 007439020 400007000 ======== 001900003 900700160 030005007 050000009 004302600 200000070 600100030 042007006 500006800 ======== 000125400 008400000 420800000 030000095 060902010 510000060 000003049 000007200 001298000 ======== 062340750 100005600 570000040 000094800 400000006 005830000 030000091 006400007 059083260 ======== 300000000 005009000 200504000 020000700 160000058 704310600 000890100 000067080 000005437 ======== 630000000 000500008 005674000 000020000 003401020 000000345 000007004 080300902 947100080 ======== 000020040 008035000 000070602 031046970 200000000 000501203 049000730 000000010 800004000 ======== 361025900 080960010 400000057 008000471 000603000 259000800 740000005 020018060 005470329 ======== 050807020 600010090 702540006 070020301 504000908 103080070 900076205 060090003 080103040 ======== 080005000 000003457 000070809 060400903 007010500 408007020 901020000 842300000 000100080 ======== 003502900 000040000 106000305 900251008 070408030 800763001 308000104 000020000 005104800 ======== 000000000 009805100 051907420 290401065 000000000 140508093 026709580 005103600 000000000 ======== 020030090 000907000 900208005 004806500 607000208 003102900 800605007 000309000 030020050 ======== 005000006 070009020 000500107 804150000 000803000 000092805 907006000 030400010 200000600 ======== 040000050 001943600 009000300 600050002 103000506 800020007 005000200 002436700 030000040 ======== 004000000 000030002 390700080 400009001 209801307 600200008 010008053 900040000 000000800 ======== 360020089 000361000 000000000 803000602 400603007 607000108 000000000 000418000 970030014 ======== 500400060 009000800 640020000 000001008 208000501 700500000 000090084 003000600 060003002 ======== 007256400 400000005 010030060 000508000 008060200 000107000 030070090 200000004 006312700 ======== 000000000 079050180 800000007 007306800 450708096 003502700 700000005 016030420 000000000 ======== 030000080 009000500 007509200 700105008 020090030 900402001 004207100 002000800 070000090 ======== 200170603 050000100 000006079 000040700 000801000 009050000 310400000 005000060 906037002 ======== 000000080 800701040 040020030 374000900 000030000 005000321 010060050 050802006 080000000 ======== 000000085 000210009 960080100 500800016 000000000 890006007 009070052 300054000 480000000 ======== 608070502 050608070 002000300 500090006 040302050 800050003 005000200 010704090 409060701 ======== 050010040 107000602 000905000 208030501 040070020 901080406 000401000 304000709 020060010 ======== 053000790 009753400 100000002 090080010 000907000 080030070 500000003 007641200 061000940 ======== 006080300 049070250 000405000 600317004 007000800 100826009 000702000 075040190 003090600 ======== 005080700 700204005 320000084 060105040 008000500 070803010 450000091 600508007 003010600 ======== 000900800 128006400 070800060 800430007 500000009 600079008 090004010 003600284 001007000 ======== 000080000 270000054 095000810 009806400 020403060 006905100 017000620 460000038 000090000 ======== 000602000 400050001 085010620 038206710 000000000 019407350 026040530 900020007 000809000 ======== 000900002 050123400 030000160 908000000 070000090 000000205 091000050 007439020 400007000 ======== 380000000 000400785 009020300 060090000 800302009 000040070 001070500 495006000 000000092 ======== 000158000 002060800 030000040 027030510 000000000 046080790 050000080 004070100 000325000 ======== 010500200 900001000 002008030 500030007 008000500 600080004 040100700 000700006 003004050 ======== 080000040 000469000 400000007 005904600 070608030 008502100 900000005 000781000 060000010 ======== 904200007 010000000 000706500 000800090 020904060 040002000 001607000 000000030 300005702 ======== 000700800 006000031 040002000 024070000 010030080 000060290 000800070 860000500 002006000 ======== 001007090 590080001 030000080 000005800 050060020 004100000 080000030 100020079 020700400 ======== 000003017 015009008 060000000 100007000 009000200 000500004 000000020 500600340 340200000 ======== 300200000 000107000 706030500 070009080 900020004 010800050 009040301 000702000 000008006大家还可以尝试另外一种方式去解决问题: 1.将每个空格的可能放置一个集合中，利用规则一消去行重复的 2.规则二消除列重复，前面两个规则重复进行 3.进行枚举，一个一个的试
