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