解数独

数独英文为sudoku,是一种在9*9 大小方格内,填充1-9 的游戏,要求每行每列,和9 个3*3 的方格内不允许有重复的数字。前几天写了一个解数独的程序:http://blog.foool.net/sudoku/ ‘set value’将方格中数字顺序填入方格内(0 代表该空格未填数字),‘compute’进行计算,规定时间内完成计算则会返回结果。右边有一个计算范例,测试过独数之道中大师级PK 题,可解。

image         image

解题有几个思路:

  1. 每行每列和方格中1-9 中任意数字只能出现一次,当在任何位置出现数字x ,就可以排除所在行、列以及方格中出现该数字x 的可能性
  2. 当某个数字x 只出现在每行、每列或者每个格子中一次,那么这个位置一定是数字x ,因为如果不是该数字x ,就不满足每行每列、每个方格都出现一次。
  3. 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()

解数独》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据