当前位置:脚本大全 > > 正文

python自动解数独教学(Python判断有效的数独算法示例)

时间:2022-01-26 01:23:14类别:脚本大全

python自动解数独教学

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

本文实例讲述了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 存在, 因此这个数独是无效的。

二、解法

代码如下:

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • #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程序设计有所帮助。

    原文链接:https://blog.csdn.net/linfeng886/article/details/82778890

    标签:
    上一篇下一篇

    猜您喜欢

    热门推荐