Sudoku Solution – Project Euler #96

This is a Python solution for Project Euler #96, to find the solution for sudokus.

The speed is modest (0.750s with pypy on Windows 7 @ i5 2.60GHz), but the code is relatively short and hopefully the idea is clear. Enjoy.
1. Find candidates for all items. If only one exists for a blank, fill it in.
2. Note down the blank with least but more than one candidates.
3. Copy the matrix and trial the candidates recursively until all blanks are filled.

def solve(mat):
    tcan = []  # list of candidates
    i = 0
    mincand = cand_i = cand_j = 10  # item with least > 1 candidates
    while (i < 9):
        j = 0
        while (j < 9):
            if mat[i][j] == 0:
                t = list(set(range(1, 10)) -
                         set([mat[x][y]
                              for x in range(i // 3 * 3, i // 3 * 3 + 3)
                              for y in range(j // 3 * 3, j // 3 * 3 + 3)] +
                             mat[i] + [mat[a][j] for a in range(9)]))
                if not t:  # can't find a candidate
                    return False
                if len(t) == 1:
                    if cand_i == i and cand_j == j:  # replacing current least
                        mincand = cand_i = cand_j = 10
                    mat[i][j] = t[0]
                    i = -1
                    continue
                if len(t) < mincand:  # saving shortest candidate list
                    tcan, mincand, cand_i, cand_j = t, len(t), i, j
            j += 1
        i += 1
    if mincand == 10:
        return mat
    else:
        for test in tcan:
            mtest = [r for r in mat]  # copy without reference
            mtest[cand_i][cand_j] = test
            mtry = solve(mtest)
            if mtry:
                return mtry
    return False

def main():
    a = open('96.txt', 'r').readlines()
    mt = []
    count = 0
    for x in a:
        if x[0] == 'G':
            mt = []
            print(x)
        else:
            mt.append(list(map(int, list(x)[0:9])))
            if len(mt) == 9:
                m = solve(mt)
                for r in m:
                    print(r)
                i = int(''.join(list(map(str, m[0][0:3]))))
                count += i
    print(count)

if __name__ == '__main__':
    main()

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据