数独

[编程题]数独

热度指数：1934 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

数独是一个非常有名的游戏。整个是一个9X9的大宫格，其中又被划分成9个3X3的小宫格。要求在每个小格中放入1-9中的某个数字。要求是：每行、每列、每个小宫格中数字不能重复。现要求用计算机求解数独。（50分）

输入描述:

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

输出描述:

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

示例1

输入

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

输出

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

算法知识视频讲解

Python

知无

华为2016研发工程师编程题

华为该套试卷中的数独有两个答案，而后台对比程序只有一个，所以一直返回有问题

用例为：

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

答案为(第7，8行不一样)：

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
3 8 6 1 4 5 9 7 2
1 2 7 9 6 8 3 5 4

对应第二个答案的代码如下：

#!/usr/bin/env python

#ret = [[i for i in range(9)] for i in range(9)]
nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

ret = []

for i in range(9):
    ret1 = map(int, raw_input().split())
    ret.append(ret1)


#ret = [[5, 0, 0, 9, 2, 0, 7, 0, 0], [0, 7, 0, 3, 4, 0, 8, 0, 0], [0, 2, 0, 0, 1, 0, 0, 5, 0], [7, 0, 4, 0, 6, 0, 1, 0, 0], [6, 0, 2, 1, 8, 3, 9, 4, 0], [0, 9, 0, 7, 5, 4, 0, 0, 8], [0, 0, 5, 8, 3, 6, 0, 7, 9], [0, 3, 9, 0, 7, 2, 6, 0, 1], [8, 0, 0, 4, 9, 1, 5, 2, 3]]

def func1(arr):
    for i in range(len(arr)):
        if 0 in arr[i]:
            return False

    return True


#get existed num set, including 0
def func2(arr, row, col):
    lst = list(arr[row])
    i1 = ((row+3)/3 - 1) * 3
    j1 = ((col+3)/3 - 1) * 3

    for i in range(9):
        lst.append(arr[i][col])

    for i in range(i1, i1+3):
        for j in range(j1, j1+3):
            lst.append(arr[i][j])

    #print "func2----------------------"
    #print row, col, lst
    lst = list(set(lst))
    return lst

def print_matrix(arr):
    for i in range(9):
        print ' '.join(map(str, arr[i]))


def func(arr, row, col):
    if func1(arr):
        lst = func2(arr, row, col)
        if len(lst) == 9:
            #print_matrix(arr)
            return True
        else:
            return False
    else:
        #arr1 = copy.deepcopy(arr)
        for i in range(9):
            for j in range(9):
                if arr[i][j] == 0:
                    lst = func2(arr, i, j)
                    lst_rest = list(set(nums) - set(lst))
                    #print i, j, lst, lst_rest
                    if not lst_rest:
                        return False
                    for n in lst_rest:
                        arr[i][j] = n
                        if func(arr, i, j):
                            return True
                        else:
                            arr[i][j] = 0
                    return False

func(ret, 0, 0)
print_matrix(ret)

发表于 2020-06-12 16:04:08 回复(0)