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

2024-11-29 18:35:59

本文实例讲述了Python判断有效的数独算法。分享给大家供大家参考，具体如下：

一、题目

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独部分空格内已填入了数字，空白格用 ‘.' 表示。

例1：

输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true

例2：

输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false

解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与示例1 相同。

但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

二、解法

先创建三个空数组 row、col、cell，以 cell 为例，里面的每个空字典都代表一个 3×3单元格，然后我们需要把数据一个个填进去
遍历整个二维数组，然后边遍历边把数组分别存入到行 row , 列 col , 3×3单元格 cell 内的字典，存为key ，而不是 value 。
然后我们就可以判断,行、列、3×3单元格对应的字典内是否已经存在board[x][y]这个键名，如果存在，那么说明重复了，返回 False
注意，字典中的值这里都为1，但是没有任何意义，你可以随意更改
把数组存入 3×3的单元格是一个难点，num = 3*(x//3)+y//3，这个式子是关键，可以找个数独，然后代入进去好好理解下
当然你也可以不用这个式子，用if/else语句来判断也行，那样比较好理解，但是不如这个式子简洁
类似于: if y<3 : ... elif 3<=y<6 : ... elif 6<=y : ...,

代码如下：

#row，col，cell分别代表行，列，3x3单元格
row, col, cell =
[{}, {}, {}, {}, {}, {}, {}, {}, {}],
[{}, {}, {}, {}, {}, {}, {}, {}, {}],
[{}, {}, {}, {}, {}, {}, {}, {}, {}]
for x in range(9):
  for y in range(9):
    #取得单元格
    num = 3*(x//3)+y//3
    temp = board[x][y]
    #不需要存入 '.'
    if temp != '.':
      if (temp not in row[x]
      and temp not in col[y]
      and temp not in cell[num]):
        row[x][temp] = '1'
        col[y][temp] = '1'
        cell[num][temp] = '1'
      else:
        return False
return True

时间 64ms，击败了 99.3%

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数组操作技巧总结》、《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

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实现自动解数独小程序

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

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

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

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

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

使用opencv对图像进行编码,一方面是图像二进制传输的需要,另一方面对图像压缩.以jpeg压缩为例: 1.转为二进制编码 img = cv2.imread(img_path) # 取值范围:0~100,数值越小,压缩比越高,图片质量损失越严重 params = [cv2.IMWRITE_JPEG_QUALITY, ratio] # ratio:0~100 msg = cv2.imencode(".jpg", img, params)[1] msg = (np.array(msg)).
python机器学习Sklearn实战adaboost算法示例详解

目录 pandas批量处理体测成绩 adaboost adaboost原理案例举例弱分类器合并成强分类器 pandas批量处理体测成绩 import numpy as np import pandas as pd from pandas import Series,DataFrame import matplotlib.pyplot as plt data = pd.read_excel("/Users/zhucan/Desktop/18级高一体测成绩汇总.xls") cond =
Python实现的求解最小公倍数算法示例

本文实例讲述了Python实现的求解最小公倍数算法.分享给大家供大家参考,具体如下: 简单分析了一下,前面介绍的最大公约数的求解方法跟最小公倍数求解方法类似,只需要改一个简单的条件,然后做一点简单的其他计算.问题的解决也是基于分解质因式的程序. 程序实现以及测试case代码如下: #!/usr/bin/python from collections import Counter def PrimeNum(num): r_value =[] for i in range(2,num+1): for
Python实现的计数排序算法示例

本文实例讲述了Python实现的计数排序算法.分享给大家供大家参考,具体如下: 计数排序是一种非常快捷的稳定性强的排序方法,时间复杂度O(n+k),其中n为要排序的数的个数,k为要排序的数的组大值.计数排序对一定量的整数排序时候的速度非常快,一般快于其他排序算法.但计数排序局限性比较大,只限于对整数进行排序.计数排序是消耗空间发杂度来获取快捷的排序方法,其空间发展度为O(K)同理K为要排序的最大值. 计数排序的基本思想为一组数在排序之前先统计这组数中其他数小于这个数的个数,则可以确定这个数的位置
Python实现的选择排序算法示例

本文实例讲述了Python实现的选择排序算法.分享给大家供大家参考,具体如下: 选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完. 选择排序每次只记录最大数的索引值. 类似于冒泡排序, 也是要比较n-1次, 区别是冒泡排序每次都交换, 选择排序只在最后比较完后才进行交换示例代码: #!/usr/bin/env python # coding:utf-8 de
纯python实现机器学习之kNN算法示例

前面文章分别简单介绍了线性回归,逻辑回归,贝叶斯分类,并且用python简单实现.这篇文章介绍更简单的 knn, k-近邻算法(kNN,k-NearestNeighbor). k-近邻算法(kNN,k-NearestNeighbor),是最简单的机器学习分类算法之一,其核心思想在于用距离目标最近的k个样本数据的分类来代表目标的分类(这k个样本数据和目标数据最为相似). 原理 kNN算法的核心思想是用距离最近(多种衡量距离的方式)的k个样本数据来代表目标数据的分类. 具体讲,存在训练样本集, 每个
Python实现的直接插入排序算法示例

本文实例讲述了Python实现的直接插入排序算法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- '''直接插入的python实现时间复杂度O(n**2) 空间复杂度O(1) 稳定思想:先将前两个元素排序,第三个元素插入前面已排好序列, 后面的元素依次插入之前已经排好序的序列 ''' author = 'Leo Howell' L = [89,67,56,45,34,23,1] def direct_insert_sort(numbers): for i in
Python实现的逻辑回归算法示例【附测试csv文件下载】

本文实例讲述了Python实现的逻辑回归算法.分享给大家供大家参考,具体如下: 使用python实现逻辑回归 Using Python to Implement Logistic Regression Algorithm 菜鸟写的逻辑回归,记录一下学习过程代码: #encoding:utf-8 """ Author: njulpy Version: 1.0 Data: 2018/04/10 Project: Using Python to Implement Logisti

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

相关推荐

随机推荐