python实现数独算法实例

yipeiwu_com5年前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程序设计有所帮助。

相关文章

python回溯法实现数组全排列输出实例分析

本文实例讲述了python回溯法实现数组全排列输出的方法。分享给大家供大家参考。具体分析如下: 全排列解释:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同...

Python制作词云的方法

Python制作词云的方法

需求: 看到朋友圈有人发词云照片,感觉自己也可以玩一玩,于是乎借助wordcloud实现功能。 环境: MacOS 10.12 +Python 2.7 +Wordcloud Windo...

python提取log文件内容并画出图表

python提取log文件内容并画出图表

之前在excel里面分析log数据,简直日了*了。 现在用python在处理日志数据. 主要涉及 matplotlib,open和循环的使用。 日志内容大致如下 2016-10-2...

Python修改文件往指定行插入内容的实例

需求:批量修改py文件中的类属性,为类增加一个core = True新的属性 原py文件如下 a.py class A(): description = "abc" 现在有一个...

Django之编辑时根据条件跳转回原页面的方法

在要跳转的编辑页面: #首先获取当期的url: curr_url = self.request.GET.urlencode() #创建一个QueryDict对象: params =...