更多课程 选择中心


Python培训

400-111-8989

Python求解数独,Python求解数独教程


《最强大脑》国际赛打开序幕,中国“酱油哥”胡宇轩战胜日本数独高手,为中国战队再加一分。12岁的数独神童胡宇轩在2017年最强大脑国际赛上打败了世界数独第一人森西亨太,而广为人知。下图是两人pk数独比赛时候的场景。

1)解数独常用的就是深度优先搜索算法,请你使用python编程,求解任意难度的数独。

import time

class point:

    def __init__(self, x, y):

        self.x = x

        self.y = y

        self.available = []

        self.value = 0

def rowNum(p, sudoku):

    row = set(sudoku[p.y * 9:(p.y + 1) * 9])

    row.remove(0)

    return row  # set type

def colNum(p, sudoku):

    col = []

    length = len(sudoku)

    for i in range(p.x, length, 9):

        col.append(sudoku[i])

    col = set(col)

    col.remove(0)

    return col  # set type

def blockNum(p, sudoku):

    block_x = p.x // 3

    block_y = p.y // 3

    block = []

    start = block_y * 3 * 9 + block_x * 3

    for i in range(start, start + 3):

        block.append(sudoku[i])

    for i in range(start + 9, start + 9 + 3):

        block.append(sudoku[i])

    for i in range(start + 9 + 9, start + 9 + 9 + 3):

        block.append(sudoku[i])

    block = set(block)

    block.remove(0)

    return block  # set type

def initPoint(sudoku):

    pointList = []

    length = len(sudoku)

    for i in range(length):

        if sudoku[i] == 0:

            p = point(i % 9, i // 9)

            for j in range(1, 10):

                if j not in rowNum(p, sudoku) and j not in colNum(p, sudoku) and j not in blockNum(p, sudoku):

                    p.available.append(j)

            pointList.append(p)

    return pointList

def tryInsert(p, sudoku):

    availNum = p.available

    for v in availNum:

        p.value = v

        if check(p, sudoku):

            sudoku[p.y * 9 + p.x] = p.value

            if len(pointList) <= 0:

                t1 = time.time()

                useTime = t1 - t0

                showSudoku(sudoku)

                print('\nuse Time: %f s' % (useTime))

                exit()

            p2 = pointList.pop()

            tryInsert(p2, sudoku)

            sudoku[p2.y * 9 + p2.x] = 0

            sudoku[p.y * 9 + p.x] = 0

            p2.value = 0

            pointList.append(p2)

        else:

            pass

def check(p, sudoku):

    if p.value == 0:

        print('not assign value to point p!!')

        return False

    if p.value not in rowNum(p, sudoku) and p.value not in colNum(p, sudoku) and p.value not in blockNum(p, sudoku):

        return True

    else:

        return False

def showSudoku(sudoku):

    for j in range(9):

        for i in range(9):

            print('%d ' % (sudoku[j * 9 + i]), end='')

        print('')

if __name__ == '__main__':

    t0 = time.time()

    sudoku = [

        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, 0, 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,

    ]

    pointList = initPoint(sudoku)

    showSudoku(sudoku)

    print('\n')

    p = pointList.pop()

    tryInsert(p, sudoku)

2)中国“酱油哥”胡宇轩对战日本数独高手的第1轮题目:标准数独三题(初级难度),如下图所示,请你用你编写的python程序,计算出下列数独的正确结果和程序运行时间。

3)中国“酱油哥”胡宇轩对战日本数独高手的第2轮题目:标准数独两题(中级难度),如下图所示,请你用你编写的python程序,计算出下列数独的正确结果和程序运行时间。

4)中国“酱油哥”胡宇轩对战日本数独高手的第3轮题目:标准数独一题(高级难度),如下图所示,请你用你编写的python程序,计算出下列数独的正确结果和程序运行时间。

(5)英国《每日邮报》报道“芬兰数学家因卡拉,花费3个月时间设计出了世界上迄今难度最大的数独游戏,而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。”下图就是那个最难数独,请你用你编写的python程序,计算出下列数独的正确结果和程序运行时间。

请自行调试程序运行结果吧。

预约申请免费试听课

填写下面表单即可预约申请免费试听! 怕学不会?助教全程陪读,随时解惑!担心就业?一地学习,可全国推荐就业!

上一篇:教你用python一秒搭建HTTP服务器
下一篇:python工程师常用的开发工具,是这三个!

Python IDE推荐7个你可能会错过的Python IDE

Python面试题之Python中爬虫框架或模块的区别

2021年Python面试题及答案汇总详解

python数据分析,你需要这些工具

  • 扫码领取资料

    回复关键字:视频资料

    免费领取 达内课程视频学习资料

Copyright © 2023 Tedu.cn All Rights Reserved 京ICP备08000853号-56 京公网安备 11010802029508号 达内时代科技集团有限公司 版权所有

选择城市和中心
黑龙江省

吉林省

河北省

湖南省

贵州省

云南省

广西省

海南省