A Numerical Chisel
A Kakuro board in the process of being solved. My competed time is 9:35 total, and about 5:32 from this point forward. See if you can beat me!
While I write the next part of our Graph Theory series, I'd like to talk about something that's been on my mind of recent.
...It's been on my mind as I'm very easily distracted by it.
It's called Kakuro, and I'd like to spend a single post giving it some love.
What is Kakuro?
Kakuro is a logic puzzle invented in Japan that works a bit like Sudoku (For reference, I'll be covering other number puzzles in future, so watch this space).
The puzzle consists of a grid of squares which are to be filled with the numbers 1 through 9. Unlike Sudoku, however, the grid is non-square: instead, the grid is made of horizontal and vertical rectangles that have been stuck together. Each of these rectangles has an associated number; these are what the numbers in the rectangle they accompany must sum to. You may not repeat a digit in a rectangle, but may repeat a digit in a different rectangle in the same row or column.
The easiest way (and often only way) to start solving a Kakuro board is using a process I call Chiselling.
What do you mean, Chiselling?
A picture of Chiselling- breaking a number down into its nonsimilar component parts.
Take a number, say 6. Now, imagine it's a big old slab of rock, like the first part of the picture on the right. Now imagine taking a chisel to it, and ending up with a bunch of smaller rocks. What we've done is chiselled it down into its component parts. The reason I call it Chiselling is that if we know part of the solution, we can break it down into a smaller problem- we chisel off the bit of the rock we know to get a smaller chunk to work with. The important thing about Chiselling is that we're not allowed to have two peices be the same size- aka, we're not allowed to have two numbers be the same in a rectangle.
It's actually easier to explain the next part of our exploration if we take a small simplification of our Kakuro game, by replacing the 1 to 9 restriction with a smaller number, say 1 to 4. This means that our clue numbers will range from 1 to 10 rather than 1 to 45, and our rectangles will have a maximum size of 4, not 9.
What is it possible to chisel with these restrictions?
The Chisel Numbers for 1 and 2 boxes.
Let's start with 1 box. It should be pretty obvious that we can have sums of 1, 2, 3 or, 4. Consequently, our boxes will be filled with 1, 2, 3, and 4, respectively. As is shown in the picture to the left, we will denote this chiselling procedure with an arrow with 2 numbers over the top: the first is the number of boxes, and the second is the maximum number we are allowed in any one box. Remember, we're not allowed to have two numbers the same!
I've also written out the chisel numbers for 2 boxes. Note that 5 has more than one solution, separated by a semicolon- we'll want to make a note of this for later.
It's now time for a practical challenge: Can you write out the chisel numbers for 3 and 4 boxes? Have a go before you continue reading!
The most important part
The Completed puzzle from earlier, as I know some of you will want the solution! Also attached is my time to completion :3
Now we have our possible chisel numbers, we can start to use them to solve our simplified game of Kakuro. Notice how most of the numbers only have one combination. In fact, the only number that has more than one combination is 5, using 2 boxes! This fact is our key; we know for a fact that every other number is determined by some combination given in our workings out. As such, we can place these numbers in our grid as small guesses, and we're well on our way to solving the puzzle. Of course, then we apply our logic to see which numbers overlap, and which are uniquely placed, and we can easily solve our puzzle. However, interestingly, using 9 numbers actually makes it both harder AND easier. While there are more combinations for each number, there are several useful giveaways- e.g. 17 in 2 boxes is always 8+9, and 30 in 4 boxes is always 9+8+7+6. As well as this, with more numbers, less combinations overlap, so it's comparatively easier to narrow down the possibilities.
Kakuro Variants
Now we've discussed the basic idea, we'll move on to the advanced class: Kakuro Variants. Here, we lift the restriction of repitition, and allow any and all digits from 1 to 9. The basic idea of chiselling is exactly the same- we just have far fewer unique chisel numbers to get us going. One can also imagine a lower bound on the numbers, e.g. using the numbers 3 through 9, but I've not come across a game using this yet. For completeness' sake, I write this as 3 numbers above the arrow: lower bound, boxes, upper bound.
That's all I wanted to say with Kakuro Variants, but I did so as I wanted to bring up an interesting and important use of this new decomposition!
Quantum Systems, AKA a very basic intro to something I actually study
A basic energy level diagram. Yes, I know real quantum particles rarely have 0 energy due to zero-point energy. We can set our energy 0 to be the zero-point energy in these cases, to get the same diagram. It's a common enough procedure that I feel justified doing it here. I'm not your physics teacher! :P
...bet you didn't see that coming, eh?
How the hell does Kakuro relate to Quantum Systems? It's all in the Energy diagram to the left. Say we have energy levels ε = 0, 1, 2, 3. We also know we have 4 particles in our system, and the total energy is 5. What arrangements of particles can we have?
This is a similar problem to our Kakuro problem. We can draw an analogy to our numbers being the energy levels of each particle, and the boxes being the particles themselves. Our total energy is therefore our box sum. In this example, we can (for instance) have 2 of the particles at ε = 0, 1 at ε = 2, and 1 at ε = 3. Alternatively, we can have 1 at ε = 0, 2 at ε = 1, and 1 at ε = 3. There are many more arrangements of these 4 particles with total energy 5. Each one of the arrangements is called a Microstate, and the state of having total Energy = 5 is called a Macrostate.
What we have begun to do is delve into the realms of Statistical Mechanics, and while I won't talk too much more about this (yet), I will say that there is a very rich and rewarding field of study hidden behind (and based upon) this very idea!
(As an aside to those who know Stat Mech already: What would a partition function of a Kakuro grid look like? Does that question even make sense?)
In Conclusion
Hopefully now you've got an explaination as to why part 2 of the Graph Theory series is taking so long. I can't just stop solving Kakuro! In addition, I hope you see why the logic we use to solve Kakuro is also very useful in science and chemistry, particularly in the discipline of Statistical Mechanics. If you've got any questions or would like to see more Stat Mech (I assume you're a rational being who wouldn't) let me know and I'll do my best to answer them.
Either way, hopefully the next Graph Theory post will be up soon! :D
-Wolfie <3
