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

(0)

相关推荐

  • php数字转汉字代码(算法)

    复制代码 代码如下: //将数字转换为汉字,比如1210转换为一千二百一十 $num = "842105580";//九位数 function del0($num) //去掉数字段前面的0 { return "".intval($num); } function n2c($x) //单个数字变汉字 { $arr_n = array("零","一","二","三","四"

  • php中最简单的字符串匹配算法

    本文实例讲述了php中最简单的字符串匹配算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <?php /* 最简单字符串匹配算法php实现方式   T: ababcabc P: abc   0.          1.          2. ababcabc    ababcabc    ababcabc |||          |||          ||| abc          abc          abc (X)          (X)         

  • php 大数据量及海量数据处理算法总结

    下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题.下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论. 1.Bloom filter 适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集 基本原理及要点: 对于原理来说很简单,位数组+k个独立hash函数.将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明

  • JQuery开发的数独游戏代码

    用了很多Jquery的插件,支持鼠标滚轮选数字.没有什么高深的技术点.工作原因很长时间没有更新了,具体代码都有些记不清了,欢迎大家来拍砖.截图:演示地址:http://demo.jb51.net/js/jsukudo/index.html下载地址:jsukudo20081110v0.3.0.5.zip 下载列表:http://code.google.com/p/jsukudo/downloads/list 用到的JS文件 文件名 出处 说明 blockUI.js http://malsup.co

  • PHP经典算法集锦【经典收藏】

    本文实例总结了PHP经典算法.分享给大家供大家参考,具体如下: 1.首先来画个菱形玩玩,很多人学C时在书上都画过,咱们用PHP画下,画了一半. 思路:多少行for一次,然后在里面空格和星号for一次. <?php for($i=0;$i<=3;$i++){ echo str_repeat(" ",3-$i); echo str_repeat("*",$i*2+1); echo '<br/>'; } 2.冒泡排序,C里基础算法,从小到大对一组数

  • c++递归解数独方法示例

    复制代码 代码如下: #include<iostream> using namespace std; void init();void function(int m); int canplace(int row,int col,int c); void outputresult(); int a[9][9], maxm = 0; int main() {   init(); function(0);  return 0; } void init(){ int i, j; for(i = 0;

  • Go语言实现的最简单数独解法

    soduku.go 复制代码 代码如下: package main import (     "fmt" ) type node []int var sudokuMay [9][9]node var Sudoku = [9][9]int{     {0, 0, 0, 0, 0, 0, 8, 0, 0},     {0, 8, 2, 4, 0, 0, 0, 0, 0},     {1, 9, 0, 0, 6, 3, 0, 0, 0},     {0, 5, 0, 0, 8, 0, 7,

  • PHP实现的方程求解示例分析

    本文实例讲述了PHP实现的方程求解.分享给大家供大家参考,具体如下: 一.需求 1. 给出一个平均值X,反过来求出来,得到这个平均值X的三个数X1 ,X2, X3,最大值与最小值的差值要小于0.4(X1-X3都是保留1位小数的数) 2. 这三个数X1, X2, X3代表了三组数.满足下面的公式: X1 = [(m1 - m2)/(m1 - m0) ] * 100 (@1); m0, m1, m2三个数的边界条件如下: 1)48<m0<51 2)0.45<m1 - m1<0.55 3

  • php编写的抽奖程序中奖概率算法

    们先完成后台PHP的流程,PHP的主要工作是负责配置奖项及对应的中奖概率,当前端页面点击翻动某个方块时会想后台PHP发送ajax请求,那么后台PHP根据配置的概率,通过概率算法给出中奖结果,同时将未中奖的奖项信息一并以JSON数据格式发送给前端页面. 先来看概率计算函数 function get_rand($proArr) { $result = ''; //概率数组的总概率精度 $proSum = array_sum($proArr); //概率数组循环 foreach ($proArr as

  • PHP实现的数独求解问题示例

    本文实例讲述了PHP实现的数独求解问题.分享给大家供大家参考,具体如下: 一.数独问题描述: 对于给出的数字二维数组,要求每行每列的数字不能重复. 二.实现代码: <?php /* 数独求解程序 * Created on 2017-4-18 * */ class Sudoku { var $matrix; function __construct($arr = null) { if ($arr == null) { $this->clear(); } else { $this->matr

  • JavaScript遍历求解数独问题的主要思路小结

    数独规则 数独游戏,经典的为9×9=81个单元格组成的九宫格,同时也形成了3×3=9个小九宫格,要求在81个小单元格中填入数字1~9,并且数字在每行每列及每个小九宫格中都不能重复. 数独技巧 直观法 候选数法 相关二十格:一个数字只与其所在行列及小九宫格的二十格相关 我的思路 精心设计了有效性判定函数,最多一次遍历81个小单元格就能做出方案的有效性判定. 同理设计了相关20格判定,一次0~9的循环就完成有效性判定. 用数组模拟堆栈,为搜索提供回溯信息. 利用对象具有map性质,来辅助判断方案的有

  • 适用于抽奖程序、随机广告的PHP概率算法实例

    那么我们在程序里必然会设计到算法,即按照一定的概率让用户获得奖品.先来看两个概率算法函数. 算法一 复制代码 代码如下: /** * 全概率计算 * * @param array $p array('a'=>0.5,'b'=>0.2,'c'=>0.4) * @return string 返回上面数组的key */function random($ps){    static $arr = array();    $key = md5(serialize($ps)); if (!isset

  • Java实现解数独的小程序

    前言 数独相信很多人都玩过,趣味性很强,十分的耐玩.可有没有程序员想过玩实现一个数独布局的算法呢?算法是个很有意思,很神奇的东西. 算法如下,需要预先给出几个固定的值,目前解决的一个最难的数独是大概26个已知值的情况,理论上应该能解决任意已知值的数独,不过不知道会不会迭代栈溢出--因为在26个已知值的情况下就迭代了3000多次了,囧~~~ 结果显示如下: 这是已知值: 1 1 2 1 4 8 1 5 5 1 6 1 1 7 7 1 8 3 2 1 1 2 2 6 2 4 4 3 5 9 3 7

随机推荐