[编程题]Sudoku
- 热度指数：99506 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入一个
的不完整数独矩阵，矩阵中的数字为
。其中，
表示该位置的数字尚未填入，
表示该位置的数字已经填入。
输出描述:
示例1
输入
0 9 2 4 8 1 7 6 3 4 1 3 7 6 2 9 8 5 8 6 7 3 5 9 4 1 2 6 2 4 1 9 5 3 7 8 7 5 9 8 4 3 1 2 6 1 3 8 6 2 7 5 9 4 2 7 1 5 3 8 6 4 9 3 8 6 9 1 4 2 5 7 0 4 5 2 7 6 8 3 1
输出
5 9 2 4 8 1 7 6 3 4 1 3 7 6 2 9 8 5 8 6 7 3 5 9 4 1 2 6 2 4 1 9 5 3 7 8 7 5 9 8 4 3 1 2 6 1 3 8 6 2 7 5 9 4 2 7 1 5 3 8 6 4 9 3 8 6 9 1 4 2 5 7 9 4 5 2 7 6 8 3 1
说明
暴力求解法，一个一个值试
def is_valid(board, row, col, num):
# 检查所在行是否有相同的数字
for i in range(9):
if board[row][i] == num:
return False # 该行已有 num，不合法
# 检查所在列是否有相同的数字
for i in range(9):
if board[i][col] == num:
return False # 该列已有 num，不合法
# 确定 3×3 小宫格的起始坐标
box_row, box_col = (row // 3) * 3, (col // 3) * 3
# 检查 3×3 小宫格是否已有 num
for i in range(3):
for j in range(3):
if board[box_row + i][box_col + j] == num:
return False # 该 3×3 小宫格已有 num，不合法
return True # 该位置可以填 num
def check(list1):
for row in range(9):
for column in range(9):
if list1[row][column] == 0:
for num in range(1,10):
if is_valid(list1, row, column, num):
list1[row][column] = num
if check(list1):
return True
list1[row][column] = 0
return False
return True
list1=[]
for i in range(9):
line_input = input().split()
line = list(map(int,line_input))
list1.append(line)
if check(list1):
for row in list1:
print(' '.join(map(str,row)))
发表于 2025-03-24 16:22:04
回复(0)
import sys
input_matrix = []
for line in sys.stdin:
if line.strip() == "":
break
else:
input_matrix.append(list(map(int, line.strip().split())))
# 另一种解法，直接使用递归，从第一个0开始填，直到填满。
# 递归逻辑如下：
# 如果当前位置是0，则尝试1到9的数字
# 选一个数字，判断当前位置填入这个数字是否合法，如果合法，则填入，继续下一个0的位置。
# 如果下一个0的位置，填的的数字也合法，继续填，直到填满。
# 如果下一个0的位置，填的的数字都不合法，返回false，当前位置填入0，然后尝试其他数字。
# 如果找到最后一个位置，都没找到0，则返回true，表示成功，递归结束，输出矩阵。
def is_valid(row_index, col_index, value):
# 判断行
for i in range(9):
if input_matrix[row_index][i] == value:
return False
# 判断列
for i in range(9):
if input_matrix[i][col_index] == value:
return False
# 判断九宫格
row_start = (row_index // 3) * 3
col_start = (col_index // 3) * 3
for i in range(row_start, row_start+3):
for j in range(col_start, col_start+3):
if input_matrix[i][j] == value:
return False
return True
def sudoku(row_index, col_index):
for i in range(0, 9):
for j in range(0, 9):
if input_matrix[i][j] == 0:
for k in range(1, 10):
if is_valid(i, j, k):
input_matrix[i][j] = k
if sudoku(i, j): # 下一个0的位置，填的的数字也合法，继续填
return True
else:
input_matrix[i][j] = 0 # 下一个0的位置，填的的数字不合法，回溯
return False # 当前位置，所有数字都不合法，返回false
if i == 8 and j == 8: # 找到最后一个位置，返回true，表示成功
return True
sudoku(0, 0)
for i in range(len(input_matrix)):
print(" ".join(map(str, input_matrix[i])))
发表于 2024-12-18 11:24:07
回复(0)
# 定义检查当前数是否可以放置在数独的某一位置
def is_valid(board, row, col, num):
# 检查行是否有重复数字
for i in range(9):
if board[row][i] == num:
return False
# 检查列是否有重复数字
for i in range(9):
if board[i][col] == num:
return False
# 检查3x3宫是否有重复数字
start_row, start_col = 3 * (row // 3), 3 * (col // 3)
for i in range(3):
for j in range(3):
if board[start_row + i][start_col + j] == num:
return False
return True
# 回溯法求解数独
def solve_sudoku(board):
for row in range(9):
for col in range(9):
# 如果当前位置为空（用0表示），则尝试放置1-9的数字
if board[row][col] == 0:
for num in range(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
# 递归尝试解决下一个空位
if solve_sudoku(board):
return True
# 回溯，如果无法解，则恢复为0
board[row][col] = 0
else:
return False
return True
# 打印数独
def print_board(board):
for row in board:
print(" ".join(str(num) for num in row))
import sys
board = [list(map(int,line.split())) for line in sys.stdin.read().splitlines()]
# 求解数独
if solve_sudoku(board):
print_board(board)
else:
print("无法解决该数独")
发表于 2024-09-23 22:32:45
回复(0)
a=[]
n=0
d=['1','2','3','4','5','6','7','8','9']
while n<9:
n+=1
a.append(input().split())
for q in range(0,9,3):
try:
temp1=[]
c1=[]
index1=[]
temp2=[]
c2=[]
index2=[]
temp3=[]
c3=[]
index3=[]
for i in range(q,q+3):
for j in range(0,3):
temp1.append(a[i][j]) #每9格放进临时列表校验
if a[i][j]=='0':
index1.append([i,j]) #记录是0的坐标
for j in range(3,6):
temp2.append(a[i][j]) #每9格放进临时列表校验
if a[i][j]=='0':
index2.append([i,j]) #记录是0的坐标
for j in range(3,6):
temp3.append(a[i][j]) #每9格放进临时列表校验
if a[i][j]=='0':
index3.append([i,j]) #记录是0的坐标
c1=[x for x in d if x not in temp1] #找到没有在1-9的数
c2=[x for x in d if x not in temp2] #找到没有在1-9的数
c3=[x for x in d if x not in temp3] #找到没有在1-9的数
for y in range(len(c1)):
a[index1[y][0]][index1[y][1]]=c1[y] #替换掉0的值
for y in range(len(c2)):
a[index2[y][0]][index2[y][1]]=c2[y] #替换掉0的值
for y in range(len(c3)):
a[index3[y][0]][index3[y][1]]=c3[y] #替换掉0的值
except:
continue
for i in range(9):
print(' '.join(a[i]))
n=0
d=['1','2','3','4','5','6','7','8','9']
while n<9:
n+=1
a.append(input().split())
for q in range(0,9,3):
try:
temp1=[]
c1=[]
index1=[]
temp2=[]
c2=[]
index2=[]
temp3=[]
c3=[]
index3=[]
for i in range(q,q+3):
for j in range(0,3):
temp1.append(a[i][j]) #每9格放进临时列表校验
if a[i][j]=='0':
index1.append([i,j]) #记录是0的坐标
for j in range(3,6):
temp2.append(a[i][j]) #每9格放进临时列表校验
if a[i][j]=='0':
index2.append([i,j]) #记录是0的坐标
for j in range(3,6):
temp3.append(a[i][j]) #每9格放进临时列表校验
if a[i][j]=='0':
index3.append([i,j]) #记录是0的坐标
c1=[x for x in d if x not in temp1] #找到没有在1-9的数
c2=[x for x in d if x not in temp2] #找到没有在1-9的数
c3=[x for x in d if x not in temp3] #找到没有在1-9的数
for y in range(len(c1)):
a[index1[y][0]][index1[y][1]]=c1[y] #替换掉0的值
for y in range(len(c2)):
a[index2[y][0]][index2[y][1]]=c2[y] #替换掉0的值
for y in range(len(c3)):
a[index3[y][0]][index3[y][1]]=c3[y] #替换掉0的值
except:
continue
for i in range(9):
print(' '.join(a[i]))
发表于 2024-08-20 20:55:22
回复(0)
##我的遇到多种解是怎么回事？？？？
num = {1, 2, 3, 4, 5, 6, 7, 8, 9}
sodu = list()
while True:
try:
sodu.append(list(map(int, input().split())))
except:
break
def find_space(data):
space = list()
for i in range(9):
for j in range(9):
if data[i][j] == 0:
space.append((i, j))
return space
def souduku(sp, data):
row, column = sp
block = list()
for i in range(row//3*3, row//3*3+3):
for j in range(column//3*3, column//3*3+3):
block.append(data[i][j])
num_row = num.difference(data[row][:])
num_column = num.difference(row[column] for row in data)
num_block = num.difference(block)
_num = num_row.intersection(num_column).intersection(num_block)
return list(_num)
def generate_soudu(_sp, sodu):
if len(_sp) == 0:
for row in sodu:
for element in row:
print(element, end=' ')
print()
else:
_num = souduku(_sp[0], sodu)
if len(_num) > 0:
row, column = _sp[0]
for j in _num:
sodu[row][column] = j
generate_soudu(_sp[1:], sodu)
sodu[row][column] = 0
space = find_space(sodu)
generate_soudu(space, sodu)
发表于 2023-10-30 19:34:42
回复(0)
def is_valid(board, row, col, num):
# Check row and column
for i in range(9):
if board[row][i] == num&nbs***bsp;board[i][col] == num:
return False
# Check 3x3 box
start_row, start_col = 3 * (row // 3), 3 * (col // 3)
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == num:
return False
return True
def solve_sudoku(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if solve_sudoku(board):
return True
board[i][j] = 0
return False
return True
def print_sudoku(board):
for row in board:
print(" ".join(map(str, row)))
# Read input
board = []
for _ in range(9):
row = list(map(int, input().split()))
board.append(row)
# Solve and print
solve_sudoku(board)
print_sudoku(board)
发表于 2023-08-16 11:04:47
回复(0)
def value(x, y):
i, j = x // 3, y // 3
grid = [m[i * 3 + r][j * 3 + c] for r in range(3) for c in range(3)]
row_val = m[x]
col_val = list(zip(*m))[y]
return {1, 2, 3, 4, 5, 6, 7, 8, 9} - set(grid) - set(row_val) - set(col_val)
def sudoku(pos):
if not pos: # 填完了
res.append([' '.join(map(str, i)) for i in m])
else:
x, y = pos[0]
val = value(x, y)
if val:
for v in val:
m[x][y] = v
sudoku(pos[1:])
m[x][y] = 0 # 回溯
m = [list(map(int, input().split())) for i in range(9)]
pos = [(x, y) for y in range(9) for x in range(9) if not m[x][y]]
res = []
sudoku(pos)
print('\n'.join(res[0]))
发表于 2023-05-06 10:40:03
回复(0)
g = [] #
for i in range(9):
g.append(list(map(int, input().split())))
# print(g)
row = [[],[],[],[],[],[],[],[],[]]
col = [[],[],[],[],[],[],[],[],[]]
three = [[],[],[],[],[],[],[],[],[]]
# print(row)
# print(col)
# print(three)
fill = []
for r in range(9):
for c in range(9):
cur = g[r][c]
if cur == 0:
# 要填的数
fill.append((r,c))
continue
# row 行的数
row[r].append(cur)
# lie 列的数
col[c].append(cur)
# three 的数
# print("r // 3 , c % 3: ", r // 3 , c // 3)
# print("r,c, ",r, c, 2 * (r // 3) + c // 3 )
three[3 * (r // 3) + c // 3].append(cur)
# print(row)
# print(col)
# print(three)
# print(fill)
def fun(index):
# for r, c in fill:
if index == len(fill):
return True
# print(">>>>:",index)
# print("--:", index, fill[index])
r, c = fill[index]
# print("r, c", r,c )
for i in range(1,10):
if i in row[r]&nbs***bsp;i in col[c]&nbs***bsp;i in three[ 3 * ( r // 3) + c // 3] :
continue
else:
# print("res:", i)
g[r][c] = i
row[r].append(i)
col[c].append(i)
three[ 3 * ( r // 3) + c // 3 ].append(i)
if fun(index + 1):
return True
row[r].remove(i)
col[c].remove(i)
three[3 * ( r // 3) + c // 3 ].remove(i)
# print("fill:", fill)
for i in range(len(fill)):
# print("***:", i)
fun(i)
for i in range(9):
for j in range(9):
print(g[i][j], end=" ")
print()
发表于 2023-02-05 22:29:47
回复(0)
#借鉴了一下评论里大佬的方法。然后用例是跑不过的自己判断过没过就行了
def check(ans,n,m,i):
if i not in ans[n] and i not in list(zip(*ans))[m]:
return True
return False
def sudoKu(res):
if len(res)==0:
return True
n,m=res[0]
for i in range(1,10):
if check(ans,n,m,i):
ans[n][m]=i
if sudoKu(res[1:]):#这里之前想的是没有做判断 所以递归有问题
return True
ans[n][m]=0#自己写到这了不晓得怎么回溯 原来这么简单
return False
ans=[]
resq=[]
for i in range(9):
ans.append(list(map(int,input().split())))
for i in range(9):
for j in range(9):
if ans[i][j]==0:
resq.append((i,j))
sudoKu(resq)
for i in ans:
print(" ".join(list(map(str,i))))
发表于 2022-08-25 09:52:46
回复(1)
大致思想DFS，加上递归回溯，python交税语言效率低，超时了，难怪没有python的解答
#向下取整
r = r // 3
c = c //3
alist = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
for rr in range(3):
row = r*3 + rr
for cc in range(3):
col = c*3 + cc
val = a[row][col]
try:
alist.remove(val)
except:
continue
return alist
def checkRowRepeat(r,a):
dic = {}
l = []
# print(a)
for i in range(9):
if a[r][i] =='0':
l.append((r,i))
continue
if a[r][i] in dic.keys():
# print('重复！ a[{}][{}] = {} {}'.format(r,i,a[r][i],dic))
return False,[(r,i)]
else:
dic[a[r][i]] = ''
# print(dic)
return True,l
def checkColRepeat(c,a):
dic = {}
l= []
for i in range(9):
if a[i][c] =='0':
l.append((i,c))
continue
if a[i][c] in dic.keys():
return False,[(i,c)]
else:
dic[a[i][c]] = ''
return True,l
#单点检查，本矩阵是否需要填充
def checker(r,c,a,q):
#压如队列
# print('加入队列({},{})'.format(r,c))
q.append((r,c))
if a[r][c] != '0':
return True
available = getMatrixMissingValues(r, c,a)
# print('a[{}][{}] 可选值 {}'.format(r, c, available))
for v in available:
# 赋值 检查 横向 检查纵向
a[r][c] = v
# print('尝试a[{}][{}]={}'.format(r,c,v))
# 行里是否有重复，无重复，本次取值可行，查看行里有没有空白
flag, empty = checkRowRepeat(r,a)
# print('尝试a[{}][{}]={} row {} {}'.format(r,c,v,flag,empty))
if flag:
if len(empty) > 0:
loc = empty[0]
re = checker(loc[0],loc[1],a,q)
if not re:
a[r][c] = '0' # 还原
# print('row尝试a[{}][{}] 可能值时，都不满足'.format(loc[0], loc[1], v))
continue
else:
# 设为该值后，行内不满足条件，尝试下一个值
a[r][c] = '0' #还原
# print('尝试a[{}][{}]={} 失败 row'.format(r, c, v))
continue
flag1, empty1 = checkColRepeat(c,a)
# print('尝试a[{}][{}]={} col {} {}'.format(r, c, v, flag1, empty1))
if flag1:
if len(empty1) > 0:
loc = empty1[0]
re = checker(loc[0],loc[1],a,q)
if not re:
a[r][c] = '0' # 还原
# print('col 尝试a[{}][{}] 可能值时，都不满足'.format(loc[0], loc[1], v))
continue
else:
# 设为该值后，行内不满足条件，尝试下一个值
a[r][c] = '0' #还原
# print('尝试a[{}][{}]={} 失败 col'.format(r, c, v))
continue
if flag and flag1:
return True
if a[r][c] == '0':
#上层取值不合理， 释放队列中所有该节点后的合法赋值
while True:
try:
tmp = q.pop()
if tmp == (r,c):
q.append((r,c))
break
else:
# print(r,c,'清除赋值 ',tmp)
a[tmp[0]][tmp[1]] = '0'
except:
break
return False
return True
a = []
while True:
try:
tmp = input().split(' ')
a.append(tmp)
except:
break
queue = []
for r in range(9):
for c in range(9):
# 为0 需要填充
if a[r][c] == '0':
# print('------------loc : ',r,c)
checker(r,c,a,queue)
else:
continue
for i in a:
print(' '.join(i))
发表于 2021-09-15 11:09:57
回复(3)
问题信息
难度：
18条回答
2237收藏
31704浏览
通过挑战的用户
查看代码-
2022-11-21 10:44:46 -
2022-09-20 23:08:44 -
2022-09-17 16:26:10
-
2022-09-16 16:52:23 -
2022-09-16 14:52:37
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
