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