数独

华为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)