python实现自动解数独小程序

跟朋友最近聊起来数独游戏，突发奇想使用python编写一个自动计算数独解的小程序。

数独的规则不再过多阐述，在此描述一下程序的主要思路：

（当前程序只针对于简单的数独，更复杂的还待深入挖掘）

1.计算当前每个空格可能的取值集合，并将空格顺序值对应取值集合置于字典中；

2.对取值集合位数为1，即空格处为单一取值的进行赋值，（填入动作），重复1刷新字典直到字典为空位置；

当前实现如下：

1.将数独输入列表中，并定义函数count_candinate_number(j)根据数独规则计算每一个为0的位置的当前可能取值：

#编辑数独题目，将题目输入列表中
question = [6,0,7,0,0,0,9,0,3,
  0,0,8,0,0,7,0,0,0,
  3,0,0,0,8,2,0,7,5,
  0,1,2,3,0,5,0,0,0,
  0,0,6,0,0,0,5,0,0,
  0,0,0,4,0,6,7,1,0,
  2,6,0,7,4,0,0,0,8,
  0,0,0,8,0,0,6,0,0,
  7,0,5,0,0,0,1,0,9]

# print(question[0])

#返回当前数独为0的空格中所有可能取值
def count_candidate_number(j):
 exist_all_number = [] #当前横竖大方格内所有出现的数字集
 candidate_number = [] #该方格内所有的数字候选集
 SD_Row = int(j) // 9 #行
 SD_Column = int(j) % 9 #列

 #用迭代器写
 exist_all_number_part1 = [question[i+SD_Row*9] for i in range(9)] #横-出现的所有数字集
 exist_all_number_part2 = [question[i*9+SD_Column] for i in range(9)] #竖-出现的所有数字集
 exist_all_number_part3 = [question[((j//9)//3)*27+((j % 9)//3)*3+i] for i in range(3)]+[question[((j//9)//3)*27+((j % 9)//3)*3+9+i] for i in range(3)]+[question[((j//9)//3)*27+((j % 9)//3)*3+18+i] for i in range(3)] #大方块-出现的所有数字集
 exist_all_number = list(set(exist_all_number_part1+exist_all_number_part2+exist_all_number_part3))  #对出现所有的数字集组合及去重
 # print(exist_all_number)

 #用循环写
 # for i in range(9):
 # if question[i+SD_Row*9] not in exist_all_number:
 #  exist_all_number.append(question[i+SD_Row*9])
 # if question[i*9 + SD_Cloumn] not in exist_all_number:
 #  exist_all_number.append(question[i*9 + SD_Cloumn])
 # # print(exist_all_number)

 #迭代器写
 candidate_number = [i for i in range(1, 10) if i not in exist_all_number] #对可能取值进行迭代输出

 #用循环写
 # for i in range(1,10):
 # if i not in exist_all_number:
 #  candidate_number.append(i)
 # print(candidate_number)

 return candidate_number

2.定义函数求解对应每个为0的位置的可能求解，并将位置信息与可能求解以键-键值的形式存储于字典中：

#对数组中每个为0的空格列出所有可能的取值数集，并放置于字典中
def all_possible_candidate_number():
 all_possible_candidate_number = {i:count_candidate_number(i) for i in range(81) if question[i] == 0}
 return all_possible_candidate_number
 # print(all_possible_candidate_number)

3.对每一个位置的可能求解进行判断，若可能解只有一个，则填入该解，循环直至数独求解完成

def main_count():
 answer_sudoku = question
 candidate_number_dic = {}
 while True:
 candidate_number_dic = all_possible_candidate_number() #在每次循环之前刷当前每个为0的空格，所有的取值集合
 if candidate_number_dic == {}:    #如果为空，则证明没有为0的空格，则为求解
  answer_sudoku = question    #对answer_sudoku赋值，并打印
  print("已求解",answer_sudoku)
  break
 else:
  for eachkey,eachValue in candidate_number_dic.items(): #对字典中位数为1的取值集合，既确定该数字变为当前应取值
  if len(eachValue) == 1:
   answer_sudoku[eachkey] = eachValue[0]
   print(eachkey,eachValue[0])   #打印对应键值及对应数值
  pass

if __name__ == '__main__':
 main_count()

程序运行结果：

D:\pythonwokr\venv\Scripts\python.exe D:/pythonwokr/数独.py
已求解 [6, 2, 7, 5, 1, 4, 9, 8, 3, 5, 4, 8, 9, 3, 7, 2, 6, 1, 3, 9, 1, 6, 8, 2, 4, 7, 5, 4, 1, 2, 3, 7, 5, 8, 9, 6, 9, 7, 6, 1, 2, 8, 5, 3, 4, 8, 5, 3, 4, 9, 6, 7, 1, 2, 2, 6, 9, 7, 4, 1, 3, 5, 8, 1, 3, 4, 8, 5, 9, 6, 2, 7, 7, 8, 5, 2, 6, 3, 1, 4, 9]

Process finished with exit code 0

程序到这里就结束了，下一步拓展是对于若不存在单独唯一解的情况，待续。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python3.6数独问题的解决

    算法比较暴力,直接用穷举的方式一个一个去试,所以程序运行时间会比较长,运行时间视数独而定. 不过从一开始到运行成功,整个过程却是一波三折,设计算法就花了不少时间,然后就是不断地去调试,找bug.刚开始的时候为了省事直接在sudoku类中递归调用blank,但是老哥还是too young too simple,sometimes navie,计算量实在是太大了,后面编译器直接抛出 "RecursionError: maximum recursion depth exceeded while cal

  • 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

  • Python如何判断数独是否合法

    介绍 该数独可能只填充了部分数字,其中缺少的数字用 . 表示. 注意事项 一个合法的数独(仅部分填充)并不一定是可解的.我们仅需使填充的空格有效即可. 解体思路 将数独按照行.列和块进行预处理,然后分别判断是否合法. 利用Python的表达式推导,匿名函数和all函数可以很方便的进行处理. 代码 class Solution: # @param board, a 9x9 2D array # @return a boolean def isValidSudoku(self, board): ro

  • 简单实现python数独游戏

    网上看到一个python写的数独,很好玩,分享给大家. import random import itertools from copy import deepcopy def make_board(m = 3): numbers = list(range(1, m**2 + 1)) board = None while board is None: board = attempt_board(m, numbers) return board def attempt_board(m, numbe

  • python实现数独游戏 java简单实现数独游戏

    使用python和java实现数独游戏,有比较才有收获哦. 1.Python版 #--coding:utf-8-- import random import itertools from copy import deepcopy def make_board(m=3): numbers = list(range(1,m**2+1)) #可能出现的数字为1-9 board = None #board是数度二维列表 while board is None: board = get_board(m,n

  • python实现解数独程序代码

    python实现解数独程序代码

    偶然发现linux系统附带的一个数独游戏,打开玩了几把.无奈是个数独菜鸟,以前没玩过,根本就走不出几步就一团浆糊了. 于是就打算借助计算机的强大运算力来暴力解数独,还是很有乐趣的. 下面就记录一下我写解数独程序的一些思路和心得. 一.数独游戏的基本解决方法 编程笼统的来说,就是个方法论.不论什么程序,都必须将问题的解决过程分解成计算机可以实现的若干个简单方法.俗话说,大道至简.对于只能明白0和1的计算机来说,就更需要细分步骤,一步一步的解决问题了. 首先来思考一下解数独的基本概念. 数独横九竖九

  • Python判断有效的数独算法示例

    本文实例讲述了Python判断有效的数独算法.分享给大家供大家参考,具体如下: 一.题目 判断一个 9x9 的数独是否有效.只需要根据以下规则,验证已经填入的数字是否有效即可. 1. 数字 1-9 在每一行只能出现一次. 2. 数字 1-9 在每一列只能出现一次. 3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次. 数独部分空格内已填入了数字,空白格用 '.' 表示. 例1: 输入: [ ["5","3",".","

  • python实现自动解数独小程序

    跟朋友最近聊起来数独游戏,突发奇想使用python编写一个自动计算数独解的小程序. 数独的规则不再过多阐述,在此描述一下程序的主要思路: (当前程序只针对于简单的数独,更复杂的还待深入挖掘) 1.计算当前每个空格可能的取值集合,并将空格顺序值对应取值集合置于字典中: 2.对取值集合位数为1,即空格处为单一取值的进行赋值,(填入动作),重复1刷新字典直到字典为空位置: 当前实现如下: 1.将数独输入列表中,并定义函数count_candinate_number(j)根据数独规则计算每一个为0的位置

  • python实现自动打卡小程序

    本文实例为大家分享了python实现自动打卡小程序的具体代码,供大家参考,具体内容如下 """ 湖南大学疫情防控每日自动打卡程序v1.0 author: Liu time:2021/3/16 """ from selenium import webdriver from selenium.webdriver.chrome.options import Options from PIL import Image from bs4 import Be

  • 用Python抢火车票的简单小程序实现解析

    利用Python制作自动抢火车票小程序,过年再也不要担心没票了! 前言 每次过年很多人都会因为抢不到火车票而回不了家,所以小编利用Python写了一个自动抢火车票的工具,希望大家能抢到火车票,回家过个好年! 我本来想自己写一个练练手的,但是转眼一想,Python 本身最大的优势是什么,不就是有很多牛逼的人已经造好轮子了吗?你只需要知道这些轮子并会使用就行了,这样会节省你大量的精力和时间,而且站在巨人的肩膀上,会看得更远. 于是我在 github 上一搜索,果然有不少抢票程序,有的是 Python

  • 详解微信小程序（Taro）手动埋点和自动埋点的实现

    每一个公司要想用户增长,都要收集和分析用户操作数据,因此埋点是必不可少的事情. 而对于前端职业发展来说,传统的手动埋点,无疑是繁琐又无聊的事情,能简化就简化. 一.手动埋点 手动埋点就是在每一处需要的地方,都加一段上报埋点的代码.影响代码的阅读体验,且散落的埋点代码不方便管理. 以页面 pv 为例,我们此前是在每一个页面中上报 pv: // src/manual/home/index.tsx import tracking from "./tracking"; // pageSn 是前

  • 基于Python实现的恋爱对话小程序详解

    基于Python实现的恋爱对话小程序详解

    目录 导语 一.小简介 二.代码演示 1)导入模块 2)倒计时 3)画2份不同的礼物 4)二种选择是不同的绘图倒计时之后就是绘制你回答的那个礼物. 5)弹窗设计的文字(可修改) 三.效果展示 1)视频展示 2)截图展示 导语 哈喽!大家好~我是木木子啦!自从写了一些表白类型的一些小脚本.小程序之后,越发不可收拾了,哈哈哈. 常常会有小粉丝说:这......小程序不够啊!刚表白去了,但是被拉黑了. 那我不答应了,我得努努力:多多益善给大家开发一些更有趣的各种各样的适合表白的小程序! 让每个人都争取

  • 从0到1使用python开发一个半自动答题小程序的实现

    前言 最近每天都有玩微信读书上面的每日一答的答题游戏,完全答对12题后,可以瓜分无限阅读卡.但是从小就不太爱看书的我,很难连续答对12道题,由此,产生了写一个半自动答题小程序的想法.我们先看一张效果图吧(ps 这里主要是我电脑有点卡,点击左边地选项有延迟) 项目GIthub地址:微信读书答题python小程序 觉得对你有帮助的请点个⭐来支持一下吧. 演示图: 做前准备 mumu模拟器 因为手边没有安卓手机,所以只能在模拟器上进行模拟,如果手上有安卓手机地,可以适当地修改一下程序.需要安装微信和微

  • python 写一个文件分发小程序

    一.概述 该小程序实现从源端到目标端的文件一键拷贝,源端和目标段都在一台电脑上面,只是目录不同而已 二.参数文件说明 1. settings.txt的说明 a. 通过配置settings.txt,填源端和目标端路径,如果用反斜杠结尾表示填的是文件夹,如果不是反斜杠结尾则代表填的是文件 b. 如果是按日期自动生成的文件夹,则用{YYYYMMMDD}或{MMDD}等替代 c. 文件支持*匹配任意名字 d. 在no_create_ok_file组中,表示不生成ok标识,在create_ok_file组

  • 详解微信小程序工程化探索之webpack实战

    详解微信小程序工程化探索之webpack实战

    前言 微信小程序因为其便捷的使用方式,以极快的速度传播开来吸引了大量的使用者.市场需求急剧增加的情况下,每家互联网企业都想一尝甜头,因此掌握小程序开发这一技术无疑是一名前端开发者不可或缺的技能.但小程序开发当中总有一些不便一直让开发者诟病不已,主要表现在: 初期缺乏方便的npm包管理机制(现阶段确实可以使用npm包,但是操作确实不便) 不能使用预编译语言处理样式 无法通过脚本命令切换不同的开发环境,需手动修改对应环境所需配置(常规项目至少具备开发与生产环境) 无法将规范检查工具结合到项目工程中(

  • 基于Python编写一个微博抽奖小程序

    基于Python编写一个微博抽奖小程序

    目录 导语 开发工具 环境搭建 先睹为快 原理简介 导语 带大家写个微博自动抽奖小程序吧,motivation和之前的B站自动抽奖小程序一样: 不想内卷了,整个B站全自动抽奖的小程序吧,万一不小心暴富了呢~ 废话不多说,让我们愉快地开始吧~ 开发工具 Python版本:3.7.8 相关模块: DecryptLogin模块: DecryptLoginExamples模块: 以及一些python自带的模块. 环境搭建 安装Python并添加到环境变量,pip安装需要的相关模块即可. 先睹为快 首先,

  • 详解微信小程序 同步异步解决办法

    详解微信小程序 同步异步解决办法 小程序中函数体还没有完成,下一个函数就开始执行了,而且两个函数之间需要传参.那是因为微信小程序函数是异步执行的.但微信小程序增加了ES6的promise特性支持,微信小程序新版本中移除了promise的支持,需要自己使用第三方库来自行实现ES6的promise特性. WxService.js import Tools from 'Tools' import es6 from '../assets/plugins/es6-promise' class Servic

随机推荐