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

相关文章

Tensorflow卷积神经网络实例进阶

Tensorflow卷积神经网络实例进阶

在Tensorflow卷积神经网络实例这篇博客中,我们实现了一个简单的卷积神经网络,没有复杂的Trick。接下来,我们将使用CIFAR-10数据集进行训练。 CIFAR-10是一个经...

使用Python导出Excel图表以及导出为图片的方法

使用Python导出Excel图表以及导出为图片的方法

本篇讲下如何使用纯python代码将excel 中的图表导出为图片。这里需要使用的模块有win32com、pythoncom模块。 网上经查询有人已经写好的模块pyxlchart,具体代...

Python制作Windows系统服务

最近有个Python程序需要安装并作为Windows系统服务来运行,过程中碰到一些坑,整理了一下。 Python服务类 首先Python程序需要调用一些Windows系统API才能作为系...

浅析Python 3 字符串中的 STR 和 Bytes 有什么区别

浅析Python 3 字符串中的 STR 和 Bytes 有什么区别

Python2的字符串有两种:str和Unicode,Python3的字符串也有两种:str和Bytes。Python2的str相当于Python3的Bytes,而Unicode相当于P...

对python多线程中互斥锁Threading.Lock的简单应用详解

对python多线程中互斥锁Threading.Lock的简单应用详解

一、线程共享进程资源 每个线程互相独立,相互之间没有任何关系,但是在同一个进程中的资源,线程是共享的,如果不进行资源的合理分配,对数据造成破坏,使得线程运行的结果不可预期。这种现象称为“...