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()