Kakuro Navigation


Kakuro is a puzzle given on a grid of red and white cells. The digits 1 to 9 must be filled into all the white cells so that they satisfy the clues given in some of the red cells. The clues specify the sum of the numbers in the row of successive white cells to the right or the column of successive white cells below. No row or column of successive white cells can have a digit repeated. In other words, we can write 4=1+3 but not 4=2+2.

Technorati tag:

Related topic: Su Doku

Digg this

Add to del.icio.us

In this page: divide and conquer, unique partitions, unique intersections, intersections, elimination, summary,

Tips and tricks: easy ways to solve Kakuro

A simple puzzle

Here is a Kakuro puzzle which will turn out to be very simple to solve. Before we start on it, let's give names to each square. We give every column a name: the first one is A, the second, B, and so on to the tenth, J. To each row we also give a name: the top row is a, the next, b, and so on to the bottom row, which is called j. Each square lies in the intersection of a row and a column, so we can name it uniquely by giving both the row and column names. For example, the bottom right square is called Jj.

In trying to solve a puzzle we will need to have a name for the unknown number that goes into a square. So, for example, when I need to talk about the number that goes into the square Jj I will write [Jj]. Similarly for any square, when you see square brackets around the name of a square, it means the number that goes into that square.

A final convention before we move on to solving the puzzle above. The left-most clue in row c involves breaking 7 into 3 parts. The left-most clue in row j involves breaking 7 into 2 parts. We will distinguish these by a subscript on the clue: 73 for the clue in row c and 72 for the other. The number is the clue, and the subscript is the number of pieces it should be broken into.

Divide and conquer

Now let us work up a strategy for splitting a puzzle into smaller pieces, because smaller puzzles are easier to solve. Take the squares Bb, Bc, Cb and Cc. The clues tell us that the sum of these four numbers taken column-wise must equal the sum of the column clues, ie, 10+13=23. But when the same four numbers are summed row-wise, then the result has to be the same. The sum in the row b has to be 17, because it must match the clue. So the remaining two numbers, [Bc] and [Cc], must add up to 23-17=6. This forces the number in [Dc] to be 1. Magic? We have converted partial knowledge about four squares into full knowledge of one square. The small 2×2 square is now isolated from the rest of the puzzle, and can be solved by itself. We have divided. Next we will conquer. But first we will state the rule.

The rule of divide and conquer

When a block of squares is connected to the rest of the puzzle through exactly one square, then call this the linking square. The value in the linking square is found as follows:

If the linking square is part of a row clue
Find the sum of all the column clues (this was 23 in the example above). Next find the sum of all the row clues except the one that involves the linking square (this was 17 in the example). Subtract this partial sum from the sum of the column clues (in the example this was 6). Subtract this number from the remaining clue to get the value in the linking square (in the example we got 7-6=1).
If the linking square is part of a column clue
Interchange column and row in the procedure given above.

Applying the rule

The linking squares can be identified without looking at the clues. They depend only on the placement of the red and white squares. We can say that the linking squares depend on the shape of the puzzle. We have circled the linking squares in the figure alongside. Now let's fill in the values using the rule of divide and conquer.

Start with the square Fd. This is part of a column clue. The sum of the row clues behind it is 3+11=14. The sum of the column clues except the one it is part of is 11. The difference is 3. Therefore [Fd]=6-3=3. It is a straightforward matter to work out [If]=9 and [Ih]=4.

It might seem that finding [Eh] is more complicated, but actually it is not. The square Eh is part of a row clue. So we first find the sum of the column clues behind it, 14+11+4=29. Next the sum of the row clues except the one to which it belongs is 6+13=19. The difference is 29-19=10. So [Eh]=19-10=9.

This tool cuts finer

The trick we have just developed actually cuts the puzzle into even smaller pieces. But before we do that, let's polish off the one square whose value we can write down without tricks. We see that [Hf]=2.

Now let's divide a bit more so that we can conquer more easily. You can easily convince yourself that you can figure out the values to be filled into the two squares which are circled in the picture alongside. Look at the square Gi. Since we have already filled in [Eh]=9, we know that [Ei]+[Ej]=13-9=4. So the 2×2 block behind Gi looks like a closed small puzzle. So Gi is a linking square. Finding the number to put down there is also strightforward. Since it is part of a row clue, take the sum of the column clues behind it: 15+(13-9)=15+4=19. From this we subtract the row clues which do not involve the linking square: 19-7=12. So we get [Gi]=17-12=5. You can go through similar reasoning to convince yourself that Ef is also a linking square which should contain the value 9.

Once Ef is filled up, it is clear that [Ff]=2. From there it is another simple step to write down [Fg]=1. With this the state of the puzzle is as shown above. Now it is time to solve the eight simpler and smaller puzzles to which we have reduced this.

Only eliminate

Consider the simple sub puzzle at the top left corner, which is extracted here. Now we use a simple fact: if you want to write 17 as the sum of two numbers, then there is only one pair which is possible: 172=9+8 (the subscript two means that you want to break up 17 into two numbers). So [Bb] can be one of 9 and 8, as shown in the figure alongside. If it is 9, then [Bc]=1, and if it is 8 then [Bc]=2. Since the row already contains a 1, the first possibility is eliminated, and we have the solution [Ba]=9. The other three squares are child's play.

The sub-puzzle shown alongside is solved in a similar way. There is an unique partition 32=1+2, that is to say, there is only one way to write 3 as the sum of two numbers. So [Gb] must be either 1 or 2. If it is 1 then [Gc]=10, and that is not allowed by the rules of Kakuro. Therefore, we must have [Gb]=2. Once you are able to fill in a single number into any square in a self-contained 2×2 block of squares, the remainder are completely fixed by the clues. So this piece of the puzzle is also done.

With a little thought, you can use the unique partition 32=1+2 to complete the 2×2 block at the bottom right hand corner of the puzzle. The block involving Dd, De, Ed, Ee is yours once you know the unique partition 42=1+3. I leave this in your, by now, capable hands.

Unique partitions

The solution of Kakuro puzzles is helped along by several unique partitions. We have used 32=1+2 and 172=9+8. Closely related are two more 42=1+3 and 162=9+7. I put down a complete list of unique partitions of length upto 4 here:
32=1+2 42=1+3 172=9+8 162=9+7
63=1+2+3 73=1+2+4 243=9+8+7 233=9+8+6
104=1+2+3+4 114=1+2+3+5 304=9+8+7+6 294=9+8+7+5
Do you see the pattern? It helps to solve things fast if you remember these partitions. But if you don't you can always look them up here.

Two unique partitions with an unique intersection

Look at the 2×2 sub-puzzle involving the squares Gg, Gh, Hg and Hh. The clue in column H is 18 and has a 2 filled in already so the remainder involves the unique partition 162. The clue in row h is 21 and has a 4 filled in already, so the remainder involves the unique partition 172. The two clues intersect at the square Hh, so [Hh] must have a value which is common to these two unique partitions. That is the number 9. This is situation that may arise often, so it is a good idea to keep a watch for unique intersections. It might be useful to keep in mind a few unique intersections; the most common ones are 32&42=1, 162&172=9, 42&73=1, 162&233=9.

Logic rules

We have now solved a large part of the puzzle. Three sub-puzzles remain. We will now solve the two remaining 2×2 pieces first. Start with the piece containing the squares Ei, Ej, Fi and Fj. Since the column E contains as clue 133, and a 9 is known, the remainder of the clue is 42. Since this is an unique decomposition, one can check each of the two possibilities for [Ei] to find the solution. Instead, I will give you a logic without using unique partitions.

The clue in row j is 72 which can be written in three ways: 72 = 1+6 = 2+5 = 3+4. Now look at which of these six numbers can go into the square Fj. Since the column clue is 152, the only possibility is [Fj]=6. Nothing else gives a single digit in Fi. It is useful to give a name to this kind of logic, because that helps us remember it. I call it "unique intersection without unique partition".

Next we take up the 2×2 block containing the squares Id, Ie, Jd and Je. This block contains the clue 62 twice. Since 62 = 1+5 = 2+4, there are 4 possibilities for [Jd]. The values 1 and 2 are ruled out because that can't give a single digit value for [Id]. Also, we know that 9 cannot appear in Id, since it appears again in the solution of the column clue. So we rule out 4 in the square Jd, leaving the value [Jd]=5. Such a process of elimination gets better the more circumstantial evidence you have.

Larger pieces need not be much tougher

One last piece of the puzzle remains. The seven squares in this piece cannot be decomposed into simpler puzzles. The column clue 42 in column D gives two possibilities in the square Dh. The possibility that [Dh]=1 is eliminated because one would then have [Ch]=9, leading to a repeated digit in the solution of the clue 193 in row h. So the solution is [Dh]=3, [Dg]=1 and [Ch]=7. This is a seconf example of elimination using circumstantial evidence.

Now there remains only a 2×2 puzzle block. The clue in column C reduces (becuase of the value already filled in Ch) to 42. Then, we get [Cg]=3, because the value 1 would lead to a repeated digit in the solution of the row clue. Elimination using circumstantial evidence again. The remaining three squares can now be filled in by a simple process of subtraction. And that's the whole big puzzle completely solved!

Tips to remember

Divide and conquer
Divide the puzzle into smaller pieces, if possible, by finding linking squares. The values in the linking squares can be easily filled in by the rule of divide and conquer. Divide and conquer sometimes can be used several times over. After one set of linking squares have been filled in, other squares may become linking squares.
Simplify using unique partitions
Some clues have an unique partition. Every unique partition reduced the number of possibilities you have to check. Some unique partitions are listed earlier in this page.
Unique intersections of unique partitions
When clues with unique partitions intersect, then sometimes we have unique intersections. Some unique intersections are listed earlier in this page.
Unique intersections without unique partitions
Sometimes you get unique intersections without unique partitions. An example was given above.
Elimination using circumstantial evidence
Elimination works better and better as you fill in more and more squares. This is the principle of elimination using circumstantial evidence.

Sourendu Gupta. Mail me if you want to reproduce any part of this page. My mailing address is a simple (satisfactory) puzzle for you to solve. Created on 8 July, 2007.