现在的位置: 首页 > 综合 > 正文

求解数独

2013年09月27日 ⁄ 综合 ⁄ 共 4019字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 按照两个规则进行
#1 如果某个格X只能填入i，则X=i
#2 如果某个数字i只能填入格X，则X=i

后来发现只要#2就能够求出解了。
代码如下，接受一个包含81个数字的字符串，对应数独的81格，未知的格用0表示。
如果没有参数则自动生成一个测试用例。

  1. import sys
  2. import os
  3. import random
  4. from array import array
  6. testcase = "164973528257816943389452167471235896538649271692781435716524389845397612923168754"
  7. keeprate = float(35)
  9. def init_groups():
  10.     groups = [[] for i in range(27)]
  11.     for i in range(81):
  12.         x = i % 9
  13.         y = i / 9
  14.         groups[y].append(i)
  15.         groups[9 + x].append(i)
  16.         groups[18 + x / 3 + y - y % 3].append(i)
  17.     return tuple(tuple(l) for l in groups)
  19. def set_table(table, groups):
  20.     for group in groups:
  21.         num = set(table[i] for i in group if type(table[i]) == int)
  22.         for s in group:
  23.             if type(table[s]) == set:
  24.                 table[s] -= num
  26. def count_table(table):
  27.     return len([item for item in table if type(item) == int])
  29. def print_table(table):
  30.     str_tab = ["" for i in range(9)]
  31.     for y in range(9):
  32.         for x in range(9):
  33.             if x != 0 and x % 3 == 0:
  34.                 str_tab[y] += " "
  35.             if type(table[x + y * 9]) == int:
  36.                 str_tab[y] += "%d " % table[x + y * 9]
  37.             else:
  38.                 str_tab[y] += "%d'" % len(table[x + y * 9])
  39.     str_tab.insert(6, "")
  40.     str_tab.insert(3, "")
  41.     print "counter = %d" % count_table(table)
  42.     print "/n".join(str_tab)
  43.     print "-------------------"
  45. def set_value(table, groups, index, value):
  46.     table[index] = value
  47.     tmp = tuple(group for group in groups if index in group)
  48.     group = set()
  49.     for g in tmp:
  50.         group |= set(g)
  51.     for item in group:
  52.         if type(item) == set:
  53.             item.discard(value)  
  55. def sudoku(table):
  56.     for i in range(81):
  57.         if type(table[i]) == int and table[i] == 0:
  58.             table[i] = set(range(1,10))
  59.     groups = init_groups()
  60.     set_table(table, groups)
  61.     count = 0
  62.     stack = []
  63.     print_table(table)
  64.     while True:
  65.         if count_table(table) == 81:
  66.             break
  67.         
  68.         flag = True
  69. #        tmp = sorted(table, key = lambda x : 10 if type(x) == int else len(x))
  70. #        for i in tmp:
  71. #            if type(i) != set or len(i) != 1:
  72. #                break
  73. #            if len(i) == 0:
  74. #                table = stack.pop()
  75. #                print "pop stack"
  76. #            table[table.index(i)] = i.pop()
  77. #            set_table(table, groups)
  78. #            flag = False
  79. #            #set_value(table, groups, table.index(i), i.pop())
  81.         for group in groups:
  82.             num = set()
  83.             total = set()
  84.             for s in group:
  85.                 if type(table[s]) == set:
  86.                     num ^= table[s] - total
  87.                     total |= table[s] - num
  88.             for s in group:
  89.                 if type(table[s]) == set:
  90.                     temp = num & table[s]
  91.                     if len(temp) == 0:
  92.                         continue
  93.                     if len(temp) == 1:
  94.                         table[s] = temp.pop()
  95.                         set_table(table, groups)
  96.                         flag = False
  97.                     else:
  98.                         table = stack.pop()
  99.         
  100.         if flag:
  101.             tmp = sorted(table, key = lambda x : 10 if type(x) == int else len(x))
  102.             if len(tmp[0]) == 0:
  103.                 continue
  104.             v = tmp[0].pop()
  105.             newtable = table[:]
  106.             for i in range(len(newtable)):
  107.                 if type(newtable[i]) == set:
  108.                     newtable[i] = newtable[i].copy()
  109.             stack.append(newtable)
  110.             table[table.index(tmp[0])] = v
  111.             set_table(table, groups)
  112.         print_table(table)
  113.             
  115. if __name__ == "__main__":
  116.     if len(sys.argv) > 1:
  117.         if len(sys.argv[1]) == 81:
  118.             init = array("c", sys.argv[1])
  119.         else:
  120.             print "Argument error!"
  121.             sys.exit(-1)
  122.     else:
  123.         init = array("c", testcase)
  124.     if init.tostring() == testcase:
  125.         for i in range(len(init)):
  126.             if random.random() >= keeprate / 100:
  127.                 init[i] = "0"
  128.     table = [int(s) for s in init]
  130.     
  131.     #set_table()
  132.     #print_table(table)
  133.     sudoku(table)

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞