python实现数独算法实例

本文实例讲述了python实现数独算法的方法。分享给大家供大家参考。具体如下：

# -*- coding: utf-8 -*-
'''
Created on 2012-10-5
@author: Administrator
'''
from collections import defaultdict
import itertools
a = [
  [ 0, 7, 0, 0, 0, 0, 0, 0, 0], #0
  [ 5, 0, 3, 0, 0, 6, 0, 0, 0], #1
  [ 0, 6, 2, 0, 8, 0, 7, 0, 0], #2
  #
  [ 0, 0, 0, 3, 0, 2, 0, 5, 0], #3
  [ 0, 0, 4, 0, 1, 0, 3, 0, 0], #4
  [ 0, 2, 0, 9, 0, 5, 0, 0, 0], #5
  #
  [ 0, 0, 1, 0, 3, 0, 5, 9, 0], #6
  [ 0, 0, 0, 4, 0, 0, 6, 0, 3], #7
  [ 0, 0, 0, 0, 0, 0, 0, 2, 0], #8
#  0, 1, 2, 3,|4, 5, 6,|7, 8
  ]
#a = [
#  [0, 0, 0, 0, 0, 0, 0, 0, 0], #0
#  [0, 0, 0, 0, 0, 0, 0, 0, 0], #1
#  [0, 0, 0, 0, 0, 0, 0, 0, 0], #2
#  #
#  [0, 0, 0, 0, 0, 0, 0, 0, 0], #3
#  [0, 0, 0, 0, 0, 0, 0, 0, 0], #4
#  [0, 0, 0, 0, 0, 0, 0, 0, 0], #5
#  #
#  [0, 0, 0, 0, 0, 0, 0, 0, 0], #6
#  [0, 0, 0, 0, 0, 0, 0, 0, 0], #7
#  [0, 0, 0, 0, 0, 0, 0, 0, 0], #8
##  0, 1, 2, 3,|4, 5, 6,|7, 8
#  ]
exists_d = dict((((h_idx, y_idx), v) for h_idx, y in enumerate(a) for y_idx , v in enumerate(y) if v))
h_exist = defaultdict(dict)
v_exist = defaultdict(dict)
for k, v in exists_d.items():
 h_exist[k[ 0]][k[ 1]] = v
 v_exist[k[ 1]][k[ 0]] = v
aa = list(itertools.permutations(range(1, 10), 9))
h_d = {}
for hk, hv in h_exist.items():
 x = filter(lambda x:all((x[k] == v for k, v in hv.items())), aa)
 x = filter(lambda x:all((x[vk] != v for vk , vv in v_exist.items() for k, v in vv.items() if k != hk)), x)
# print x
 h_d[hk] = x
def test(x, y):
 return all([y[i] not in [x_[i] for x_ in x] for i in range(len(y)) ])
def test2(x):
 return len(set(x)) != 9
s = set(range(9))
sudokus = []
for l0 in h_d[0 ]:
 for l1 in h_d[ 1]:
  if not test((l0,), l1):
   continue
  for l2 in h_d[ 2]:
   if not test((l0, l1), l2):
    continue
   # 1,2,3行 进行验证
   if test2([l0[ 0], l0[ 1], l0[ 2]
      , l1[ 0], l1[ 1], l1[ 2]
      , l2[ 0], l2[ 1], l2[ 2]
      ]) : continue   
   if test2([l0[ 3], l0[ 4], l0[ 5]
      , l1[ 3], l1[ 4], l1[ 5]
      , l2[ 3], l2[ 4], l2[ 5]
      ]) : continue   
   if test2([l0[ 6], l0[ 7], l0[ 8]
      , l1[ 6], l1[ 7], l1[ 8]
      , l2[ 6], l2[ 7], l2[ 8]
      ]) : continue   
   for l3 in h_d[ 3]:
    if not test((l0, l1, l2), l3):
     continue
    for l4 in h_d[ 4]:
     if not test((l0, l1, l2, l3), l4):
      continue
     for l5 in h_d[ 5]:
      if not test((l0, l1, l2, l3, l4), l5):
       continue
      # 4，5，6行 进行验证
      if test2([l3[ 0], l3[ 1], l3[ 2]
         , l4[ 0], l4[ 1], l4[ 2]
         , l5[ 0], l5[ 1], l5[ 2]
         ]) : continue   
      if test2([l3[ 3], l3[ 4], l3[ 5]
         , l4[ 3], l4[ 4], l4[ 5]
         , l5[ 3], l5[ 4], l5[ 5]
         ]) : continue   
      if test2([l3[ 6], l3[ 7], l3[ 8]
         , l4[ 6], l4[ 7], l4[ 8]
         , l5[ 6], l5[ 7], l5[ 8]
         ]) : continue   
      for l6 in h_d[ 6]:
       if not test((l0, l1, l2, l3, l4, l5,), l6):
        continue
       for l7 in h_d[ 7]:
        if not test((l0, l1, l2, l3, l4, l5, l6), l7):
         continue
        for l8 in h_d[ 8]:
         if not test((l0, l1, l2, l3, l4, l5, l6, l7), l8):
          continue
         # 7，8，9行 进行验证
         if test2([l6[ 0], l6[ 1], l6[ 2]
            , l7[0 ], l7[1 ], l7[2 ]
            , l8[0 ], l8[1 ], l8[2 ]
            ]) : continue   
         if test2([l6[ 3], l6[ 4], l6[ 5]
            , l7[3 ], l7[4 ], l7[5 ]
            , l8[3 ], l8[4 ], l8[5 ]
            ]) : continue   
         if test2([l6[ 6], l6[ 7], l6[ 8]
            , l7[6 ], l7[7 ], l7[8 ]
            , l8[6 ], l8[7 ], l8[8 ]
            ]) : continue   
         print l0
         print l1
         print l2
         print l3
         print l4
         print l5
         print l6
         print l7
         print l8
         sudokus.append((l0, l1, l2, l3, l4, l5, l6, l7, l8))

希望本文所述对大家的Python程序设计有所帮助。

网趣网上购物系统HTML静态版

网趣购物系统静态版支持网站一键静态生成，采用动态进度条模式生成静态，生成过程更加清晰明确，商品管理上增加淘宝数据包导入功能，与淘宝数据同步更新!采用领先的AJAX+XML相融技术，速度更快更高效！系统进行了大量的实用性更新，如优化核心算法、增加商品图片批量上传、谷歌地图浏览插入等，静态版独特的生成算法技术使静态生成过程可随意掌控，从而可以大大减轻服务器的负担，结合多种强大的SEO优化方式于一体，使

下载