# Euler Problem 96 – Sudoku I’ve been looking forward to this one for some time. Its fairly easy to solve a Sudoku. But creating an algorithm for every possible solution is quite a bit harder.

I started by modelling the grid and then iterating each cell to determine possible options. The plan was that once I found a cell that only had one remaining option, I would plug that number in and start the routine all over again. Eventually the grid would be solved. But the sneaky Euler problem writers, they loaded each grid so that no such cell existed. The closest was 2 choices. I would need a recursive routine.

So I found some brilliant routines in Haskell and Perl that treat each grid as a string, rather than a model. I translated and modified for my needs. Here’s what I came up with. Works like a charm.

``` class Solver: sum = 0 def checkSame(self, i, j): flag = False if i/9 == j/9: flag = True if (i-j) % 9 == 0: flag = True if i/27 == j/27 and (i % 9)/3 == (j % 9)/3: flag = True return flag def solveRecursive(self, subset): i = subset.find('0') if i == -1: print subset self.sum += int(subset[0:3]) excluded = set() for j in range(81): if self.checkSame(i, j): excluded.add(subset[j]) for n in '123456789': if n not in excluded: self.solveRecursive(subset[:i] + n + subset[i+1:]) if __name__ == '__main__': S = Solver() grid = "" f = open("sudoku.txt", "r") for row in f.readlines(): if row != "G": grid += row[0:9] if len(grid) == 81: print grid S.solveRecursive(grid) grid = "" else: print "\nWorking on:", row[0:7], "SubTotal:", S.sum f.close() print "Answer =", S.sum ```