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[0] != "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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s