Programming on my Birthday

As an extension of the last post, I’ve been ramping up applying Python to solving more and more difficult puzzles I find from the puzzle-makers on Twitter, especially Yohaku and 1to9Puzzle. The simple ones are just too easy for the solver to zip through randomly and print out the solution. The challenging work is already done, so it’s time to move on to a more difficult challenge. Thankfully, the puzzlers have us covered.

Here’s a Yohaku puzzle which requires you to fill in the squares with 9 consecutive numbers, with the totals of the rows and columns given.

yohaku_May_27.png

How should we start? Pick random collections of 9 consecutive numbers and crank through all their possible combinations? That would take a while. There’s a way to find out the starting number, as I was reminded by a fellow puzzler who replied to one of the posts. The row totals are 15, 22 and 26. That means if you add up all nine numbers, you get 15 + 22 + 26 = 63. The total of the column sums is also 63. There’s a formula for the sum of an arithmetic sequence:

puzzle_post1.png

S is the sum of the sequence, which we know is 63. n is the number of numbers, which is 9. The only unknowns are a1, which is the first number in the sequence, and an, which is the last number. But the last number we know will be the first number plus 8, so we can fill in the values we know and solve for a1:

puzzle_post2.png

Our starting number is 3. For those of you who may not like the algebraic way of finding the starting number, you can easily add up 9 consecutive numbers using Python, and find out which starting number gives you 63. Like this:

puzzle_post3.png

This confirms the starting number is 3. Now I can just solve the puzzle the same way I did before, by making Python choose a random order of the numbers 3 through 11 and check if they give the correct row and column totals. But this is taking a while! How many different combinations, I mean permutations of those numbers could there be? 9 factorial is only 362,000.

Permutations to the Rescue

We’re probably getting a lot of repetition in the random lists, so there’s a way to generate all the permutations of the numbers 3 through 11 one by one, check them, and move on to the next one without repeating ourselves. First you have to import the permutations function from Python’s itertools package and tell it the list you want to sample from:

from itertools import permutations
...
perms = permutations(list(range(start_num,start_num+9)),9)

Then, in the infinite loop, we’ll generate the next permutation and check it as before.

a,b,c,d,e,f,g,h,i = next(perms)

Randomly assigning numbers didn’t get me a solution within a reasonable amount of time. This method found the solution instantly:

Our solution, in 0.1 seconds!

Our solution, in 0.1 seconds!

Check the row and column totals and sure enough, they all work. What an accomplishment to solve a more difficult problem using more powerful tools! We had to do a little searching (algebraically or otherwise) to find the starting number, then we were waiting and waiting for our answer, so we used itertools to search through the permutations without repeating ourselves.

Another puzzle falls to the mighty power of Python! Next: Backtracking to “guess and check” square by square.

And it’s my birthday.