Brute force

We worked once at a code Dojo on how to generate some valid sudokus. The conclusion was “that’s not that simple” and especially when you try to figure out by yourself what could be an algorithm. In the 2 hours allocated to solve that problem, no team manage to get to an algorithm which do not “always” lead to a dead-end (whatever your next choice, the sudoku would not be valid). Pure brute force didn’t work.

ROUND 1 Sudoku 1 - Me 0.

I met few months later “machine learning” through the really good book “Programming Collective Intelligence” and when I reached the chapter on genetic algorithm, I remembered I’ve been defeated by a sudoku generator problem.

1,2,3 fight.

Naive algorithm

Genetic algorithm are a family of algorithm which mimic gene behaviour. That mutates and crossovers. A really simple explanation is you define a set of elements (called gene) which evolve during each iteration (called generation). To create a new generation, you have few possibilities:

• You mutate slightly a gene
• You crossover two genes
• You create a new random gene

You don’t really need to understand fully how that works to already get something which works if you get the right weapon to help you. Mine is PyGene.

After having read more than 5 pages on it, after having discovered PyGene library, I felt the outcome would be certain.

ROUND 2

You should start with a gene and PyGene provide many implementations for some common genes. Sudokus are somehow a list of 81 integers. I copied the demo_string_int.py example code and slightly customised the code to make it match my problem.

The only real things to understand here is the fittest function. Knowing a try, that should return a positive number which match how far it is from the solution. In our case, how far from valid the sudoku is. You can’t only say “is valid True or False”, else the algorithm would not be able to compare 2 invalid solutions. They would be equally invalid.

I like to use python set to check for validity. Assuming all numbers are between 1 and 9, a sudoku is valid if and only if all lines, columns and blocks contains 9 different elements, ie if the set with all elements has a length of 9.

To get something which return 0 if valid and a big number if there is many errors in the sudoku, you just need to subtract the number of elements in the set from 9. If one number is missing, you get 1, if 2 you get 2, etc…

def fittest(sudoku):
    result = 0
        for l in sudoku:
           line = set(l)
           result += NB_VAL_LINE - len(line)
        for i in range(NB_VAL_LINE):
            column = set(line[i] for line in sudoku)
            result += NB_VAL_LINE - len(column)
        for x in range(NB_BLOCK):
            for y in range(NB_BLOCK):
                block = set(sudoku[x*NB_BLOCK + xshift][y*NB_BLOCK + yshift] for xshift in range(NB_BLOCK) for yshift in range(NB_BLOCK))
                result += NB_VAL_LINE - len(block)
        return result

The full code is available here.

The fight started. Best score is dropping quickly and…. You wait for almost ever. You could have won but that’s definitely too slow. After around 2 hours, more than 100000 generations, the best try has a score of 38 (0 is the target). Still far.

Sudoku 2 - Me 0

Clever try

The previous failure can be explained quite easily. The algorithm was smart enough to generate a number between 1 and 9 for each gene, nothing more. Even if you already have a 9 in the row, the algorithm would try randomly a 9. We need to upgrade our weapon.

Instead of having 81 integer values, what if we code a list of 9 lines with values from 1 to 9 shuffled. A mutation would not be a random number between 1 and 9 but a random permutation between numbers.

We can’t rely anymore on the IntGene implementation provided by PyGene, we need to code our own. Fortunately, almost no other code has to be changed.

class LineGene(BaseGene):
    def __add__(self, other):
        return choice([self.value, other.value])

    def mutate(self):
        indexes = range(9)
        shuffle(indexes)
        x,y = indexes[:2]
        self.value[x], self.value[y] = self.value[y], self.value[x]

    def randomValue(self):
        values = range(1,10)
        shuffle(values)
        return values

Three functions should be defined.

• How to generate a random value: let’s just shuffle a list of 1 to 9.
• How to mutate: let’s take two random indexes between 0 and 8 and swap two elements.
• How to merge: let’s take one or the other gene, randomly.

ROUND 3

I got to the score 38 in 200 generations and 3 seconds. Much faster and stayed around 29 for ever (reached at 100 000+ generations).

Sudoku 3 - Me 0

There is plenty of parameters to play with. Not understanding deeply how genetic algorithms work do not allow you to tune them other than empirically. I changed many of them, started to understand some issues. Too much diversity and an average too far from my best score. I tuned and tuned again for more stability.

29 at 2500 generations after few seconds. Much better.

but my patience wouldn’t allow me to wait for days to get a valid result. After more than a night, the algorithm is now at 24. Full code here.

… Sudoku 4 - Me 0