首页 > 试题广场 >

Sudoku

[编程题]Sudoku
  • 热度指数：99506 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据 9 \times 9 盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个 3 \times 3 粗线宫内的数字均含 1 \sim 9 这九个数字，且不重复。

\hspace{15pt}保证输入的数独是合法的，且存在唯一解。

输入描述:
\hspace{15pt}输入一个 9 \times 9 的不完整数独矩阵，矩阵中的数字为 0 \sim 9 。其中，0 表示该位置的数字尚未填入，1 \sim 9 表示该位置的数字已经填入。


输出描述:
\hspace{15pt}输出一个 9 \times 9 的完整数独矩阵。
示例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

说明

\hspace{15pt}在这个样例中，输入的数独如下图一所示，输出的是数独的唯一解，如下图二所示。


算法知识视频讲解
添加回答
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头像 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头像 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头像 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条回答 31703浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Sudoku

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号