首页 > 试题广场 >

Sudoku

[编程题]Sudoku

热度指数：92380 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9，并且不重复。

例如：

输入

输出

数据范围：输入一个 9*9 的矩阵

输入描述:

包含已知数字的9X9盘面数组[空缺位以数字0表示]

输出描述:

完整的9X9盘面数组

示例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

算法知识视频讲解

Python

大溪地渔民

def has_repetition(n, i, j, matrix):
    for k in range(9):
        if k!=j and matrix[i][k]==n:
            return True
        if k!=i and matrix[k][j]==n:
            return True
    a, b = i-i%3, j-j%3
    for x in range(a, a+3):
        for y in range(b, b+3):
            if not (i==x and j==y) and matrix[x][y]==n:
                return True
    return False


def sudo(n, matrix):
    i, j = n//9, n%9
    if matrix[i][j]:
        if n == 80:
            return True
        return sudo(n+1, matrix)
    for k in range(1, 10):
        if not has_repetition(k, i, j, matrix):
            matrix[i][j] = k
            if n==80&nbs***bsp;sudo(n+1, matrix):
                return True
            matrix[i][j] = 0
    return False


while True:
    try:
        matrix = []
        for _ in range(9):
            matrix.append(list(map(int, input().split())))
        
        sudo(0, matrix)
        for i in range(9):
            print(" ".join(list(map(str, matrix[i]))))
    except:
        break

发表于 2020-12-17 12:28:52 回复(0)

Python

纪铭

复制下面那位兄弟的代码，但修改成了python3.9版本的

#-*- coding: utf8 -*-

def check(matrix,row,col,value):
    """
    检测在(row,col)放value是否合适
    1.每行含1-9,不含重复值value
    2.每列含1-9,不含重复值value
    3.3*3区块含1-9,不含重复值value
    """
    #检测每行
    for j in range(9):
        if matrix[row][j]==value:
            return False
    #检测每列
    for i in range(9):
        if matrix[i][col]==value:
            return False
    #检测元素所在3*3区域
    area_row=(row//3)*3
    area_col=(col//3)*3
    for i in range(area_row,area_row+3):
        for j in range(area_col,area_col+3):
            if matrix[i][j]==value:
                return False
    return True

def solveSudoku(matrix,count=0):
    """
    遍历每一个未填元素，遍历1-9替换为合适的数字
    """
    if (count==81):#递归出口
        return True
    row=count//9#行标
    col=count%9#列标
    if (matrix[row][col]!=0):#已填充
        return solveSudoku(matrix,count=count+1)
    else:#未填充
        for i in range(1,10):
            if check(matrix,row,col,i):#找到可能的填充数
                matrix[row][col]=i
                if solveSudoku(matrix,count=count+1):#是否可完成
                    return True#可完成
                #不可完成
                matrix[row][col]=0#回溯
        return False#不可完成

matrix=[]
for i in range(9):
    matrix.append(list(map(int,input().split(' '))))
solveSudoku(matrix)
for i in range(9):
    print(' '.join(map(str,matrix[i])))

编辑于 2020-12-02 12:44:08 回复(0)

Python

gagnon

def Possible(x, y, n):
    global grid
    for i in range(9):
        if grid[i][y] == n:
            return False
    for i in range(9):
        if grid[x][i] == n:
            return False
    x0 = x//3 * 3
    y0 = y//3 * 3
    for i in range(3):
        for j in range(3):
            if grid[x0 + i][y0 + j] == n:
                return False
    return True

def solve():
    global grid
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                for n in range(1, 10):
                    if Possible(i, j, n):
                        grid[i][j] = n
                        solve()
                        grid[i][j] = 0
                return
    res = ''
    for i in grid:
        for j in i:
            res = res + '%d '%j
        res = res.strip() + '\n'
    print(res[:-1])

while True:
    try:
        grid = []
        for i in range(9):
            grid.append(list(map(int, input().split())))
        solve()
    except:
        break

参考油管大神的算法

发表于 2020-07-27 09:08:12 回复(0)

Python

心怀高远，脚踏实地

def check(sod,loc,value):
    x, y = loc//9,loc%9
    row = sod[x]
    column = list(b[y] for b in sod)
    x1,y1 = (x//3)*3,(y//3)*3
    L1,L2,L3 = sod[x1][y1:y1+3],sod[x1+1][y1:y1+3],sod[x1+2][y1:y1+3]
    matrix = L1+L2+L3
    allnum = row+column+matrix+[0]
    if value in allnum:
        return False
    else:
        return True

def solver(sodoku:list):
    total = []
    def search(sodo:list,nowloc=0):
        if nowloc == 81:
            for i in sodo:
                print(' '.join(list(map(str,i))))
            return True
        x, y = nowloc//9,nowloc%9
        if sodo[x][y] == 0:
            for i in range(1,10,1):
                if check(sodo,nowloc,i):
                    sodo[x][y] = i
                    if search(sodo,nowloc+1):
                        return True
                    else:
                        sodo[x][y] = 0
            return False
        else:
            search(sodo,nowloc+1)
        return False
    search(sodoku,0)
    return total
for i in range(1):
    try:
        mylist = []
        for i in range(9):
            mylist.append(list(map(int,input().split())))
        solver(mylist)
    except:
        break

题目不完整，缺少粗线框的限制

发表于 2020-05-01 17:04:33 回复(0)

Python

Hao_jiu_bu_jian

为什么自己运行能通过，提交确只是部分正确，行数都不对？

case通过率为33.33%

测试用例:
0 0 8 7 1 9 2 4 5
9 0 5 2 3 4 0 8 6
0 7 4 8 0 6 1 0 3
7 0 3 0 9 2 0 0 0
5 0 0 0 0 0 0 0 0
8 6 1 4 0 3 5 2 9
4 0 0 0 2 0 0 0 8
0 0 0 0 0 0 0 7 0
1 0 7 0 6 8 0 5 0

对应输出应该为:

6 3 8 7 1 9 2 4 5
9 1 5 2 3 4 7 8 6
2 7 4 8 5 6 1 9 3
7 4 3 5 9 2 8 6 1
5 9 2 6 8 1 4 3 7
8 6 1 4 7 3 5 2 9
4 5 6 3 2 7 9 1 8
3 8 9 1 4 5 6 7 2
1 2 7 9 6 8 3 5 4

你的输出为:

6 3 8 7 1 9 2 4 5
9 1 5 2 3 4 7 8 6
2 7 4 8 5 6 1 9 3
7 4 3 5 9 2 8 6 1
5 9 2 6 8 1 4 3 7
8 6 1 4 7 3 5 2 9

4 5 9 3 2 7 6 1 8

def solver(board, rows, cols, squs, i, j):
    if i>=9: return True

    if board[i][j]!='0':
        return solver(board, rows, cols, squs, (i*9+j+1)//9, (i*9+j+1)%9)

    for n in {'1','2','3','4','5','6','7','8','9'}-(rows[i]|cols[j]|squs[i//3*3+j//3]):
        board[i][j] = n
        rows[i].add(n)
        cols[j].add(n)
        squs[i//3*3+j//3].add(n)

        if not solver(board, rows, cols, squs, (i*9+j+1)//9, (i*9+j+1)%9):
            board[i][j] = '0'
            rows[i].remove(n)
            cols[j].remove(n)
            squs[i//3*3+j//3].remove(n)
        else:
            return True
    return False

while True:
    try:
        board = []
        for i in range(9):
            board.append(input().split())
        
        rows, cols, squs = [set() for i in range(9)], [set() for i in range(9)], [set() for i in range(9)]
        for i, row in enumerate(board):
            for j, num in enumerate(row):
                if num!='0':
                    rows[i].add(num)
                    cols[j].add(num)
                    squs[i//3*3+j//3].add(num)
        solver(board, rows, cols, squs, 0, 0)
        for i in range(9):
            print(' '.join(board[i]))
    except:
        break

编辑于 2017-09-08 13:47:21 回复(0)

Python

woowHentai

import sys

def checkone(each):

m=0

for i in each:

if i !=0:

if each.count(i)>1:

return False

else:

m+=1

else:

m+=1

if m==9:

return True

def getblock(s,i):

l=[]

for j in range(3):

for k in range(3):

l.append(s[i/3*3+j][i%3*3+k])

return l

def check(s):

a=b=c=0

#check row

for i in range(9):

if checkone(s[i]):

a+=1

else:

return False

#check col

for i in range(9):

t=[]

for j in range(9):

t.append(s[j][i])

if checkone(t):

b+=1

else:

return False

#check block

for i in range(9):

l=getblock(s,i)

if checkone(l):

c+=1

else:

return False

if a==b==c==9:

return True

def sudo(s,num):

#print num

c=''

if check(s):

if num==81:

for i in s:

string=''

for j in i:

string+=str(j)

c+=' '.join(string)+'\n'

c=c.strip()

print c

return True

else:

if out[num/9][num%9]!=0:

s[num/9][num%9]=out[num/9][num%9]

return sudo(s,num+1)

else:

for j in range(1,10):

s[num/9][num%9]=j

if sudo(s,num+1):

return True

else:

s[num/9][num%9]=0

while True:

try:

s=[]

for i in range(9):

s.append(map(int,raw_input().split()))

out =s

#print s

sudo(s,0)

except:

break

#这个题有问题，存在多解~~~

发表于 2017-08-17 16:54:26 回复(0)

提交观点

问题信息

搜索思维基础数学

难度：

6条回答 2050收藏 28201浏览

通过挑战的用户

查看代码

IceToSnow

2022-11-21 10:44:46
水田夏木

2022-09-20 23:08:44
牛客56293...

2022-09-17 16:26:10
牛客48014...

2022-09-16 16:52:23
lingyao

2022-09-16 14:52:37

Sudoku

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题