首页 > 试题广场 >

数独

[编程题]数独

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

数独是一个我们都非常熟悉的经典游戏，运用计算机我们可以很快地解开数独难题，现在有一些简单的数独题目，请编写一个程序求解。

如有多解，输出一个解

输入描述:

输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的。

输出描述:

输出九行，每行九个空格隔开的数字，为解出的答案。

算法知识视频讲解

Python

wili_lan

while True:
try:
board = [ [int(i) for i in input().split()] for j in range(9)]

row = [set(range(1, 10)) for _ in range(9)] # 行剩余可用数字
col = [set(range(1, 10)) for _ in range(9)] # 列剩余可用数字
block = [set(range(1, 10)) for _ in range(9)] # 块剩余可用数字

empty = [] # 收集需填数位置
for i in range(9):
for j in range(9):
if board[i][j] != 0: # 更新可用数字
val = int(board[i][j])
row[i].remove(val)
col[j].remove(val)
block[(i // 3)*3 + j // 3].remove(val)
else:
empty.append((i, j))

def backtrack(iter):
if iter == len(empty): # 处理完empty代表找到了答案
return True
i, j = empty[iter]
b = (i // 3)*3 + j // 3
for val in row[i] & col[j] & block[b]:
row[i].remove(val)
col[j].remove(val)
block[b].remove(val)
board[i][j] = val
if backtrack(iter+1):
return True
row[i].add(val) # 回溯
col[j].add(val)
block[b].add(val)
return False
backtrack(0)

for i in range(9):

print(' '.join(str(j) for j in board[i] ))
except:break

发表于 2022-09-11 00:38:27 回复(0)

Python

牛客888340459号

Recursive with DFS pruning

def findNext(board,row_ind,col_ind):
    for row in range(row_ind,9):
        for col in range(col_ind,9):
            if int(board[row][col])==0:
                return row,col

    for row in range(9):
        for col in range(9):
            if int(board[row][col])==0:
                return row,col
    return -1,-1

def check_valid(board,row_ind,col_ind,temp):
    for i in range(9):
        if temp == int(board[i][col_ind]):
            return False
        if temp == int(board[row_ind][i]):
            return False
    ini_row=(row_ind//3)*3
    ini_col=(col_ind//3)*3
    for row in range(3):
        for col in range(3):
            if int(board[row+ini_row][col+ini_col]) == temp:
                return False
    return True


def solveSudoku(board,row_ind=0,col_ind=0):
    row_ind,col_ind=findNext(board,row_ind,col_ind)
    if row_ind == -1:
        return True

    for temp in range(1,10):
        if check_valid(board,row_ind,col_ind,temp):
            board[row_ind][col_ind]=str(temp)
            if solveSudoku(board,row_ind,col_ind):
                return True
            board[row_ind][col_ind]='0'
            
    return False

try:
    while True:
        board=[]
        for i in range(9):
            board.append(input().split(' '))
        if solveSudoku(board):
            for i in range(9):
                print(' '.join(board[i]))
except:
    pass

发表于 2021-11-04 03:17:25 回复(0)

Python

牛客723029601号

def isOk(mat,i,j,num):
    #判断行中有无此数，有输出F
    if num in mat[i]:
        return False
    #判断列中有无此数，有输出F
    if num in [mat[x][j] for x in range(9)]:
        return False
    #判断所在格子里有无此数，有输出F
    ii,jj = i//3*3,j//3*3
    piece = []
    for k in range(3):
        for l in range(3):
            piece.append(mat[ii+k][jj+l])
    if num in piece:
        return False
    #剩下的情况都合法，输出T
    return True
 
def remain(mat,i,j):
    remain_list=[]
    for num in range(1,10):
        if isOk(mat,i,j,str(num)):
            remain_list.append(str(num))
    remain_list.append('0')
    return remain_list
 
def all_remain(mat):
    all_remain_list=[]
    for i in range(9):
        for j in range(9):
            if mat[i][j] == '0':
                remain_list = remain(mat,i,j)
                all_remain_list.append({'index':(i,j),'remain_list':remain_list,'remain_num':len(remain_list)})
    all_remain_list=sorted(all_remain_list,key=lambda e:e.__getitem__('remain_num'))
    return all_remain_list
 
def dfs(mat,all_remain_list,n):
    if n == len(all_remain_list):
        return mat
    else:
        (i,j) = all_remain_list[n]['index']
        for num in all_remain_list[n]['remain_list']:
            if num == '0':
                return
            if isOk(mat,i,j,num):
                mat[i][j] = num
                result = dfs(mat,all_remain_list,n+1)
                if type(result) == type(None):
                    mat[i][j] = '0'
                    continue
                else:
                    return result
            else:
                continue
 
mat=[]
for i in range(9):
    mat.append([x for x in input().split()])
mat = dfs(mat,all_remain(mat),0)
for row in mat:
    print(' '.join(row))

对之前的答案做了些改进，先填容易填的空，减少搜索时间

编辑于 2020-02-14 16:41:06 回复(0)

Python

duanluheng

解题思路:

1、先搞懂数独的游戏规则

2、回溯法+剪枝函数

# coding: utf8
import sys

sudoku_arr = [[]]
queued = [[], [], [], [], [], [], [], [], []]
candidate_value = [1, 2, 3, 4, 5, 6, 7, 8, 9]
finded = False


def set_queued():
    col = 0
    while col < 9:
        row = 0
        while row < 9:
            if sudoku_arr[row][col] != 0:
                queued[col].append(sudoku_arr[row][col])
            else:
                pass
            row += 1
        col += 1


def back_trace(row, col):
    global finded
    global sudoku_arr
    global queued
    # 说明已经检测完了
    if finded:
        return
    if row == 8 and col == 9:
        for line in sudoku_arr:
            print " ".join(str(i) for i in line)
        finded = True
        return
    # 该换行了
    elif row < 8 and col == 9:
        row += 1
        col = 0
    # 如果row，col上有值，则跳过，直接测试下一个
    if sudoku_arr[row][col] != 0:
        return back_trace(row, col + 1)
    # 进行测试
    for i in candidate_value:
        # 如果本行，或者本列出现过i，则i不可取，不会对
        # 全局结果产生任何影响，直接找下一个值，进行测试
        if i in sudoku_arr[row]&nbs***bsp;i in queued[col]:
            continue
        row_tmp = (row / 3) * 3
        error = False
        # 判断所属的小的9宫格内是否重复
        while row_tmp < (row / 3) * 3 + 3:
            col_tmp = (col / 3) * 3
            while col_tmp < (col / 3) * 3 + 3:
                if i == sudoku_arr[row_tmp][col_tmp]:
                    error = True
                    break
                col_tmp += 1
            if error:
                break
            row_tmp += 1
        if error:
            continue
        # 在row行和col列中都没出现过，则记录下来
        # print "sudoku_arr[%d][%d]=%d" % (row, col, i)
        queued[col].append(i)
        sudoku_arr[row][col] = i
        back_trace(row, col + 1)
        sudoku_arr[row][col] = 0
        queued[col].pop(-1)
    # for循环走完,说明没有适合该位置的值,
    # 也说明之前有错误的值,不必进一步试探下去,直接返回
    return


try:
    lines = 0
    arrs = []
    while True:
        line = raw_input()
        if line == "":
            break
        else:
            lines += 1
            arrs.append([int(i) for i in line.split(" ")])
            sudoku_arr = arrs
            if lines == 9:
                set_queued()
                back_trace(0, 0)
                lines = 0
                break
        sys.exit(0)
except Exception, e:
    sys.exit(1)

由于一部分输入的解并非唯一解，因此代码得出的解和系统得出的不一定完全一致，因此，通过率不到100%。但代码是没问题的，可以通过对行求和，对列求和都等45进行验证

发表于 2020-01-02 18:26:52 回复(0)

Python

离疏

import sys
def isOk(mat, i, j,num):#判断填入数字是否合法
    for row in range(0,9):#遍历该列，若该数字已出现过，则不合法
        if mat[row][j] == num:
            return False
    for col in range(0,9):#遍历该行，若该数字已出现过，则不合法
        if mat[i][col] == num:
            return False
    ii = i//3
    jj = j//3
    for row in range(ii*3,ii*3+3):#遍历该位置所处的3*3矩阵，若该数字已出现过，则不合法
        for col in range(jj*3,jj*3+3):
            if mat[row][col] == num:
                return False
    return True

def dfs(mat,i,j):#深度优先遍历
    if i==9:#所有行已遍历完，则结束
        return mat
    if j==9:#所有列已遍历完，则进入到下一行
        return dfs(mat,i+1,0)
    flag = False#flag表示该行有需要填充的格子
    for col in range(j,9):#遍历该行的所有列，如果有值为0，则需要进行填充
        if mat[i][col]==0:
            flag = True
            isChange =False#ischange表示是否已进行填充
            for num in range(1,10):
                if isOk(mat,i,col,num):#找出1-9中能够合法填入的数字
                    isChange =True
                    mat[i][col] = num
                    tpp = dfs(mat,i,col+1)#将该位置填充后，该行的后续位置是否有解
                    if tpp == None:#如果后续位置无解，则将该位置重新置为0，未填充状态
                        isChange = False
                        mat[i][col] = 0
                        continue#尝试下一个数字
                    else:
                        return  tpp
            if isChange==False:#找不到合法数字进行填充
                return None
    if flag==False:#该行所有位置已填满，进入到下一行
        return dfs(mat,i+1,0)
    
while True:
    isCon = True
    mat = []
    for i in range(9):
        line = sys.stdin.readline().strip()
        if not line:
            isCon = False
            break
        line =[int(i) for i in line.split(' ')]
        mat.append(line)
    if isCon ==False:
        break
    mat = dfs(mat,0,0)
    for line in mat:
        print(' '.join(str(j) for j in line))

发表于 2018-08-09 10:54:48 回复(2)

Python

大鹌鹑

import sys

ALL_SET = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
matrix = []
row_available = []
col_available = []
block_available = [[ALL_SET.copy() for _ in xrange(3)] for _ in xrange(3)]
positions = []


# print block_available

def sudoku(step=0):
    if step == len(positions):
        for i in xrange(9):
            print ' '.join(matrix[i])
        print
        return
    pos_x, pos_y = positions[step]
    block_x, block_y = pos_x / 3, pos_y / 3
    for num in row_available[pos_x].intersection(col_available[pos_y]).intersection(
            block_available[block_x][block_y]):
        matrix[pos_x][pos_y] = num
        row_available[pos_x].remove(num)
        col_available[pos_y].remove(num)
        block_available[block_x][block_y].remove(num)
        sudoku(step + 1)
        row_available[pos_x].add(num)
        col_available[pos_y].add(num)
        block_available[block_x][block_y].add(num)


for _ in xrange(9):
    input_args = sys.stdin.readline()
    row = input_args.split()
    matrix.append(row)
    row_available.append(ALL_SET - set(row))

for i in xrange(9):
    col_available.append(ALL_SET - {matrix[n][i] for n in xrange(9)})

for i in xrange(9):
    for j in xrange(9):
        if matrix[i][j] == '0':
            positions.append((i, j))
        else:
            block_x, block_y = i / 3, j / 3
            block_available[block_x][block_y].remove(matrix[i][j])

sudoku(0)

发表于 2016-08-10 15:29:14 回复(0)