首页 > 试题广场 >

合法数独

[编程题]合法数独
  • 热度指数:815 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个数独板的输入,确认当前的填法是否合法。
合法的输入需要满足以下三个条件:
1. 每一行的9个格子中是1-9的9个数字,且没有重复
2. 每一列的9个格子中是1-9的9个数字,且没有重复
3. 9个3*3的小格子中是1-9的9个格子,且没有重复

输入描述:
输入9行字符串,每行9个字符(不包含\r\n),总共81个字符,空着的格子用字符‘X’表示

53XX7XXXX
6XX195XXX
X98XXXX6X
8XXX6XXX3
4XX8X3XX1
7XXX2XXX6
X6XXXX28X
XXX419XX5
XXXX8XX79


输出描述:
合法在输出字符串,“true”
非法则输出字符串,“false”
示例1

输入

53XX7XXXX
6XX195XXX
X98XXXX6X
8XXX6XXX3
4XX8X3XX1
7XXX2XXX6
X6XXXX28X
XXX419XX5
XXXX8XX79

输出

true
tem1 = [None] * 9
#输入
for i in range(9):
    tem1[i] = list(input())

flag = 1
for i in range(9):
    for j in range(9):
        if tem1[i][j] != 'X' and tem1[i].count(j) > 1:
            flag = 0

if flag == 1:
    (3239)#做一个转置,然后利用上边的方法判断
    tem2 = [[None] * 9 for _ in range(9)]
    for i in range(9):
        for j in range(9):
            tem2[j][i] = tem1[i][j]
            
    for i in range(9):
        for j in range(9):
            if tem2[i][j] != 'X' and tem2[i].count(j) > 1:
                flag = 0

#判断3*3的小方块是否满足要求
(3240)#首先将小方块中展开为一列
if flag == 1:
    tem3 = []
    for ii in range(3):
        for jj in range(3):
            for iii in range(ii*3, (ii+1)*3):
                for jjj in range(jj*3, (jj+1)*3):
                    tem3.append(tem1[iii][jjj])
            for m in tem3:
                if m != 'X' and tem3.count(m) > 1:
                    flag = 0
                    break
            tem3 = []
                    
if flag == 1:
    print('true')
else:
    print('false')
参考的是已通过的那位大佬的答案,这里做个记录
思路就是分别判断每一行是否满足要求
判断列的时候做一个交换,判断3*3的时候重组为一行
发表于 2020-03-21 22:50:04 回复(0)