`
xlaohe1
  • 浏览: 128960 次
  • 性别: Icon_minigender_1
  • 来自: 来处
社区版块
存档分类
最新评论

9x9数独算法

阅读更多
下面给出了源代码
sdks文件里面含有120个数独
请各位大大纠正

这个算法也可以用来做生成数独,然后取出几个
比如你给定数独为
000000000000000000000000000000000000000000000000000000000000000000000000000000001
# 嘿嘿,这解可多了,机器别跑死了。


# -*- coding:utf-8 -*-
'''
首先生成9x9x9的三维数组,每个值为[1,2,3,4,5,6,7,8,9]
1,然后确定有独一的值,清除行,列,块当中的值 clean(data)函数
继续1
然后找到唯一值,即行、列或块当中只出现一次的值,设置当前值,然后执行1,clean_help(data)函数
最后如果没有唯一值那就找最少候选的那个格子先尝试这个格子的其中一个候选,再尝试剩余的候选数字
'''

#1. 先遍历一遍,找出所有“只有一个候选数字”的格子, 清除行,列,块数据
#2. 填满这些数字,重复第一步
#3. 如果没有“只有一个候选数字”的格子,那就找最少候选的那个格子
#  先尝试这个格子的其中一个候选,再尝试剩余的候选数字
from copy import deepcopy
# 移除数组中指定的值
def rm(s, n):
    i = 0
    try:
        s.remove(n)
        i = i + 1
    except:
        pass
    return i
# 根据行,列坐标,返回行,列,块数组
def find(fbs, i, j):
    block = [] 
    br = i / 3 * 3
    bc = j / 3 * 3
    for l in range(0, 3):
        r = br + l
        for k in range(0, 3):
            c = bc + k
            block.append(fbs[r][c])
    return {"row":fbs[i], "column":[fbs[a][j] for a in range(0, 9)], "block":block}
# 打印
def pnt(dbss):
    print "============"
    for i in range(0, 9):
        print dbss[i], "\n" 
# 生成9×9×9的三维数组
base = [[[i for i in range(1, 10)] for a in range(1, 10)] for b in range(1, 10)]
sudo1 = [
        [0,8,1, 0,9,0, 0,0,0], 
        [0,0,0, 1,0,7, 0,5,0],
        [0,7,5, 0,4,0, 0,0,1],
        [0,0,0, 0,3,4, 2,0,0],
        [5,0,0, 7,0,1, 0,0,0],
        [0,0,0, 0,0,2, 1,0,9],
        [0,0,6, 0,8,0, 0,0,4],
        [8,0,7, 6,0,0, 5,0,0],
        [0,0,3, 0,0,0, 6,0,8]
        ]
# 此数独没有解出来。
sudo2 = [ 
                [ 8, 0, 0, 0, 0, 0, 0, 0, 0 ], 
                [ 0, 0, 3, 6, 0, 0, 0, 0, 0 ], 
                [ 0, 7, 0, 0, 9, 0, 2, 0, 0 ], 
                [ 0, 5, 0, 0, 0, 7, 0, 0, 0 ], 
                [ 0, 0, 0, 0, 4, 5, 7, 0, 0 ], 
                [ 0, 0, 0, 1, 0, 6, 0, 3, 0 ], 
                [ 0, 0, 1, 0, 0, 0, 0, 6, 8 ],  
                [ 0, 0, 8, 5, 0, 0, 0, 1, 0 ], 
                [ 0, 9, 0, 0, 0, 0, 4, 0, 0 ]  
                   ]
                   
# 此数独有解,但死循环                   
sudo3 = [
         [0, 0, 0, 0, 1, 0, 0, 0, 0],
         [0, 0, 0, 2, 0, 3, 0, 0, 0],
         [0, 0, 4, 0, 0, 0, 5, 0, 0],
         [0, 6, 0, 0, 0, 0, 0, 7, 0],
         [8, 0, 0, 0, 5, 0, 0, 0, 9],
         [0, 7, 0, 0, 0, 0, 0, 6, 0],
         [0, 0, 5, 0, 0, 0, 4, 0, 0],
         [0, 0, 0, 3, 0, 2, 0, 0, 0],
         [0, 0, 0, 0, 9, 0, 0, 0, 0]
         ]
sudo4 = [
         [0, 0, 0, 0, 1, 0, 8, 7, 0],
         [0, 2, 0, 0, 9, 0, 0, 0, 0],
         [0, 0, 0, 5, 0, 0, 0, 0, 0],
         [2, 0, 0, 0, 6, 8, 0, 9, 0],
         [0, 0, 8, 0, 7, 0, 3, 0, 0],
         [0, 9, 7, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 4, 6, 3, 0],
         [0, 8, 0, 0, 5, 0, 0, 0, 0],
         [0, 7, 1, 3, 0, 0, 9, 0, 0]
         ]

sudo5 = [
             [0,0,2,4,5,0,7,0,0]
            ,[0,4,0,0,0,8,0,3,0]
            ,[8,0,1,0,0,3,5,0,6]
            ,[0,5,3,0,0,0,0,0,4]
            ,[7,0,0,0,0,0,0,0,2]
            ,[2,0,0,0,0,0,6,7,0]
            ,[3,0,6,5,0,0,1,0,7]
            ,[0,2,0,1,0,0,0,5,0]
            ,[0,0,7,0,2,9,4,0,0]
         ]

# 初始化填充base
def inits(b, s):
    for i in range(0, 9):
        sudo = s[i]
        for j in range(0, 9):
            num = sudo[j]
            if num != 0:
                b[i][j] = [num]
                finds = find(b, i, j)
                for f in finds:
                    ff = finds[f]
                    for fff in ff:
                        if len(fff) > 1:
                            rm(fff, num)
    return b
            
# 根据独一值,清除行,列,块值                            
def clean(clean_data):
    flag = True
    while flag:
        # 退出条件
        rms = 0
        for i in range(0, 9):
            for j in range(0, 9):
                num = clean_data[i][j]
                if len(num) == 1:
                    # 根据独一值清除行,列,块
                    finds = find(clean_data, i, j)
                    for f1 in finds:
                        f2 = finds[f1]
                        for f3 in f2:
                            if len(f3) > 1:
                                rms += rm(f3, num[0])
        if rms == 0:
            flag = False
    return clean_data
# 找到唯一值,并清除行列块
def clean_help(data):
    while True:
        # 退出条件
        flag = True
        for i in range(0, 9):
            for j in range(0, 9):
                brk = 0
                cur = data[i][j]
                if len(cur) > 1:
                    finds = find(data, i, j)
                    for f in finds:
                        a = [0] * 9
                        f1 = finds[f]
                        for f2 in f1:
                            for f3 in f2:
                                a[f3 - 1] += 1
                        for m in cur:
                            # 找到了唯一值,并进行设置,清除数独,退出当前循环
                            if a[m - 1] == 1:
                                flag = False
                                brk = 1
                                data[i][j] = [m]
                                clean(data)
                                break
                        if brk == 1:
                            break
        # 当没有唯一值是退出循环
        if flag:
            break
    return data

# 读取数独源
def readSdks(i):
    sudokus = open("sdks", "r")
    if i < 0 or i > 125:
        print "Not found sudoku data"
        return
    sdk = sudokus.readlines()[i].replace("\n","")
    sdks = [sdk[j:j + 9] for j in range(0, 81, 9)]
    #print sdks
    ret = [[int(sk[l]) for l in range(0, 9)] for sk in sdks]
    sudokus.close()
    
    return ret
    
# 验证数独    
def isOk(data):
    for i in range(0, 9):
        for j in range(0, 9):
            finds = find(data, i, j)
            for f in finds:
                a = [0] * 9
                ff = finds[f]
                for fff in ff:
                    if len(fff) > 1:
                        return False
                    a[fff[0] - 1] += 1
                for ia in a:
                    if ia > 1 or ia == 0:
                        return False
    print  "ok"
    return True

# 找到数独当中最小候选对象元祖
#([], x, y) 数组为候选可能值,x为行坐标,y为列坐标
def small(data):
    ret_sm = ([0] * 9, -1, -1)
    for i in range(0, 9):
        for j in range(0, 9):
            if len(data[i][j]) > 1 and len(data[i][j]) < len(ret_sm[0]):
                ret_sm = (data[i][j], i, j)
    return ret_sm

# 最后数独完成操作 设置候选值
def done(data):
    if isOk(data):
        pnt(data)
        return
    sm_tuple = small(data)
    #print sm_tuple
    if sm_tuple[1] == -1:
        #print "no solve"
        return
    # 设置候选值
    for sm in sm_tuple[0]:
        #pnt(data)
        # 复制数独源,上次的结果不然还存在,就不能求多解了
        copy_data = deepcopy(data)
        # 设置候选值
        copy_data[sm_tuple[1]][sm_tuple[2]] = [sm]
        # 然后执行清除操作
        copy_data = clean_help(clean(copy_data))
        if isOk(copy_data):
            #print "in done"
            pnt(copy_data)
            return
        # 如果没有完成,继续设置候选值
        done(copy_data)


def main():
    for i in range(0, 120):
        print "The %d index" % i
        #readSdks(1)
        sudokuData = readSdks(i)
        base = [[[j for j in range(1, 10)] for a in range(1, 10)] for b in range(1, 10)]
        init_data = inits(base, sudokuData)
        #print "init:"
        #pnt(init_data)
        clean_data = clean(init_data)
        #print "clean:"
        #pnt(clean_data)
        only_data = clean_help(clean_data)
        #print "only:"
        #pnt(only_data)
        done(only_data)
        
if __name__ == "__main__":
    main()

0
2
分享到:
评论

相关推荐

    数独9X9_MATLAB数独_数独9x9在线_9x9数独_数独_求解9X9数独_

    下面将详细探讨如何利用MATLAB实现9x9数独的求解。 1. **基本概念** - **数独定义**:数独是一种基于9x9网格的逻辑游戏,每个网格被划分为9个小的3x3宫格。目标是填充空白单元格,使得每一行、每一列和每个小宫格...

    9x9数独 计算程序[C++]

    标题中的"9x9数独计算程序[C++]"指的是一个使用C++编程语言编写的解决9x9标准数独问题的程序。数独是一种逻辑游戏,玩家需要在9x9的网格中填入数字,使得每一行、每一列以及每个3x3的小宫格内的数字都从1到9不重复。...

    数独算法,数独游戏

    数独是一种广受欢迎的逻辑推理游戏,它基于一个9x9的网格,被分为9个3x3的小宫格。每个宫格内需填入数字1到9,使得每行、每列以及每个小宫格内的数字都不重复。数独的解决方法多种多样,其中一种常见的是基于回溯的...

    数独算法,C语言编写,注释很详细。

    在这个压缩包中,包含了一个名为“数独算法.cpp”的C语言源代码文件,用于实现数独的求解算法。 首先,我们来看数独问题的表示。在C语言中,通常会用二维数组来表示数独的矩阵。例如,定义一个9x9的二维数组,数组...

    易语言数独算法

    在编程领域,实现数独算法是一项有趣的挑战,尤其在易语言这样的中文编程环境中。易语言数独算法主要涉及以下几个关键知识点: 1. **数组和二维数据结构**:数独盘面通常表示为一个9x9的二维数组,其中包含9个3x3的...

    用C++完成数独算法

    在本文中,我们将探讨如何使用C++来实现数独算法,一种解决9x9数独谜题的方法。数独是一种逻辑游戏,目标是填满9x9的网格,使得每一行、每一列以及每一个3x3的小宫格(也称为子网格)都包含数字1到9,且每个数字在每...

    SudokuSolver:解决 9x9 数独问题

    数独是一种广受欢迎的逻辑谜题,它基于一个9x9的网格,被分为9个3x3的小宫格。每个宫格、行和列都包含数字1到9,且每个数字在各自的宫格、行和列中只能出现一次。`SudokuSolver`是一个专门用于解决这种问题的程序,...

    基于挖洞思想的数独游戏生成算法

    数独游戏通常由9x9的网格构成,其中包含已知数字,游戏的目标是用1至9的数字填满剩余的空格,且要求每一行、每一列以及每一个3x3的子网格中的数字都不重复。数独游戏的生成算法是其核心,而挖洞思想是一种创新的数独...

    java数独题库高效生成算法代码

    Java数独题库高效生成算法代码是用于创建各种难度级别的9x9数独谜题的程序。数独是一种逻辑推理游戏,目标是在一个9x9的网格中填入数字,使得每一行、每一列以及每一个3x3的小宫格内的数字都从1到9不重复。这种算法...

    matlab数独算法

    在给定的标题“matlab数独算法”中,我们讨论的是如何使用MATLAB编程语言来实现数独的自动填充算法。 MATLAB是一种高级编程环境,常用于数值计算、符号计算、数据可视化和图像处理等任务。由于其简洁的语法和强大的...

    自编的数独解算算法代码,C++

    这个“自编的数独解算算法代码,C++”是使用C++编程语言实现的算法,旨在帮助解决9x9的数独谜题。 首先,让我们理解C++编程语言。C++是C语言的一个扩展,具有面向对象的特性,是软件开发中常用的高级编程语言之一。...

    回溯法解9*9数独

    9x9数独是一个经典的逻辑游戏,目标是填充一个9x9的网格,使得每一行、每一列以及每一个3x3的小宫格(也称为子区域)都包含从1到9的所有数字,并且每个数字在每一行、每一列和每个小宫格中都只能出现一次。...

    人工智能之回溯法python求解9X9数独

    给出求解9*9数独至少一种搜索方法(回溯、爬山、模拟退火,束搜索、遗传算法),并分析其算法的性能(四个搜索算法评价指标)。 答: 回溯: 深度优先搜索+变量分配,即每次分配一个变量+约束检查,即考虑与前面分配...

    数独算法Java版。(有注释,编译已过)

    数独是一种基于逻辑的数字填充游戏,通常在9x9的格子中进行,分为9个小的3x3宫格。玩家需要根据已给出的数字,用1到9的数字填充空格,使得每一行、每一列以及每一个小宫格内的数字都不重复。在IT领域,实现数独算法...

    Objective-C 9宫格数独算法

    在Objective-C中实现9宫格数独算法,我们可以从以下几个方面进行探讨: 1. **数据结构**:首先,我们需要一个合适的数据结构来存储数独的当前状态。一种常见的方式是使用二维数组,如`int sudoku[9][9]`,其中0表示...

    数独游戏算法(C实现)

    数独游戏是一种流行的逻辑游戏,玩家需要填充一个9x9的矩阵,使得每行、每列和每宫中都包含数字1-9,且每个数字只能出现一次。数独游戏算法的目的是使用计算机程序来自动解决数独游戏。 本文将对数独游戏算法进行...

    shudu.rar_java 数独算法_shudu_数独

    本项目是一个用Java实现的数独算法,结合了一个用户界面,便于玩家交互。 在Java中实现数独算法,通常涉及以下关键点: 1. **数据结构设计**:首先,我们需要一个数据结构来存储数独的当前状态。这通常是一个二维...

    数独程序算法,有用的算法

    在Java中,我们可以创建一个`SudokuBoard`类来表示数独棋盘,棋盘可以是一个9x9的二维数组,其中每个元素代表一个单元格,初始时部分单元格已有数字,其余为空待填充。`SudokuBoard`类需要包含方法来检查某个数字...

    java数独生成算法及基于此算法的android数独游戏APK

    在APK文件"Sudoku.apk"中,除了核心的数独算法实现外,还包含了Android应用的资源文件(如布局文件、图片、音频等)、AndroidManifest.xml(应用配置)、以及其他必要的组件。用户可以通过安装这个APK在Android设备...

Global site tag (gtag.js) - Google Analytics