python实现数独算法实例

yipeiwu_com6年前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最长回文串算法

给定一个字符串,要求在这个字符串中找到符合回文性质的最长子串。所谓回文性是指诸如 “aba”,"ababa","abba"这类的字符串,当然单个字符以及两个相邻相同字符也满足回文性质。...

Python使用itchat 功能分析微信好友性别和位置

Python使用itchat 功能分析微信好友性别和位置

这样就将你所有微信好友的信息都返回了,我们并不需要这么多的信息,我们选取一些信息存储到 csv 文件中 注意:返回的信息是一个 list,其中第一个是我自己的信息,所以要从第二项开始...

Python实现对象转换为xml的方法示例

本文实例讲述了Python实现对象转换为xml的方法。分享给大家供大家参考,具体如下: # -*- coding:UTF-8 -*- ''''' Created on 2010-4-...

python二进制文件的转译详解

首先导入所需的包:import struct struct有以下几个主要的函数: # 按照给定的格式(fmt),把数据封装成字符串(实际上是类似于c结构体的字节流) pack(fmt...

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

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