Wednesday, January 11, 2012

Basics of Kenken Puzzles

If you don't know the rules of KenKen then you can refer to www.kenken.com for an excellent source of daily puzzles which also explains the rules. I'll summarise it as best I can, it's a puzzle where you need to fill in each cell such that each row and cell contains a unique sequence of numbers respectively. If you are more familiar with Sudoku, it's similar in terms of the fact that each row/column can only contain one 1, one 2, one 3.. one 9. In KenKen's case, you are allowed to use numbers 1,2...,n. Where n is the size of the puzzle. However, unlike Sudoku you must ensure each 'cage' (bolded subareas on the puzzle) adds, multiplies, subtracts or divides to the target number listed on the a top-left corner of the cage. Subtraction and Divisions can be done in any order, so 2 / 4 and 4 / 2 both match 2/ (division). However, the constraints of unique numbers must be adhered to at all times. For more information, just refer to www.kenken.com.

Today we will be solving and walking through a simple 6x6 KenKen puzzle (from www.kenken.com). There are several important concepts which will make your puzzle solving much simpler. KenKen can seem daunting at first, but it's a solvable puzzle without guessing! There is always a way to deduce/use logic to fill in the cells without trial and error. I hope to highlight some of these through this given KenKen puzzle:



So, how do we get started? We don't exactly have any free single 1x1 cage to immediately write down. Usually if there is a simple 1x1 cage you should write down those numbers first because they can give hints to surrounding cages in similar rows/columns.

Now note that today we are solving a 6x6 puzzle, hence we are only allowed to fill in numbers 1 to 6. This is important to note because it limits the number of possibilities for each cage. One of the first things I tend to look for first - is a cage in which I immediately know what numbers are contained in those cages but not necessarily the right order. For a 6x6 puzzle, you should look primarily for 11+ and 5- cages. Why is this? It's because there is only one possibility for each of the cages, namely 5 and 6, and 1 and 6 respectively. (Question: If it was a 8x8 puzzle, what numbers should you be looking for?) Don't worry too much about the ordering at the moment - the correct ordering will come as we fill the puzzle. Noting these down we get:



We can also note several one possibility cages, 15x = 3 * 5. There is no other way of multiplying two numbers less than 6 to equal 15. There's also another subtle one, 36x. How many possibilities does this have? Well it seems like there may be a few, 6*6*1, 6*3*2, 3*3*4. However, in our puzzle 36x exists in a row which means there can be no repeated terms in the factoring! Hence we can rule out 6*6*1 and 3*3*4 being valid possibilities for the 36x cage. This just leaves a single possibility, 6*3*2! Anymore cages that only have one possibility? 20x also looks tempting - let's see, 5*4*1 and 5*2*2. But wait! Again, 20x is on a row and can't have any repeated elements so it just leaves one possibility: 5*4*1! There may be more but let's just put these on the puzzle first:



You may note that we actually haven't even filled a single entry yet! This is quite normal, you'll slowly realise that many possibilities will start collapsing when you fill a few in!

Now we will employ a more tricky technique which is immensely useful in solving KenKen puzzles. In Mathematics, this is called the Pigeonhole Principle. Essentially, the Pigeonhole Principle states that if you have n items and wish to place them into m boxes with n > m, then at least 1 box will contain more than 1 item. How on earth are we going to apply this to the puzzle? We need to look in a vertical manner - note how the 3 rightmost columns (4th to 6th columns) already contain 4 possibilities of having a 5 in them? Wait! 4 possibilities in 3 columns that violates the rules of the puzzle! Hence, one of these must not belong in the 3 rightmost columns. Now look at the bottom-most 11+, the 5 in this cage can exist on the 3rd column! Therefore, if this puzzle has a solution the 5 must belong in the 3rd column. So let's fill this in...




Now the bottom-most 11+ cage must have 6 in the unfilled cell. Now you notice that it also fills in the other 11+ cage in the 3rd row! Because the number 6 exists in the 4th column, it means the 3rd row 11+ cage must have number 6 in the 5th column. This then cascades to 36x! The number 6 for 36x (2*3*6) must go to the rightmost column otherwise it will violate the other 2 columns that we just filled in. For Sudoku solvers this should be in your familiar territory! That one observation allowed us to chain-complete a portion of the puzzle:



What else can we fill in? It's important to consider new point of views after you have filled in a set of entries because by filling in correct positions for cages - it reduces the possibilities for cages that are related to it (relation comes from the single 1 to 6 constraint on the rows/columns). If we observe the 3/ (division) cage on the rightmost column, previously it has the possibility of 3/1, 6/2. However now that we have filled in 6 on the rightmost column, the only possibility is 3/1. If you jot this down on the cage, you notice that we can now fill in 15x because the number 3 in 3*5=15 cannot belong to the rightmost column anymore so hence we have uniquely determined the correct position. Again, a lot of cascading solutions - by solving the 15x, we now know the position of the 5 in 20x and the position in 3x (validate it for yourself). If you fill in the details you'll get something like the following:



Now it looks much better! At this stage, we can fill in 24x because we know the product of its divisors cannot contain a 3 as it will violate the first row only having one 3 (it's taken by the 15x). 24x = 1*4*6. Note that it also can't be 2*2*6 because it exists in a single row and we can't have duplicate elements because it'll violate the rules. Note that the 4- cage on the leftmost column can be uniquely identified to be 6-2. How did we do this?

There are actually multiple ways to view this - the simplest is to note that the first row possibilities are completely filled except for one number. We have used 1,4,6 for 24x and 3,5 for 15x. That leaves only the possibility of 2 in the left and uppermost cell. Now we can't put negative numbers so the only possibility for the other cell in the cage is 6 - making 6-2=4.

The other way to view this will prove to be more useful when solving larger KenKen puzzles. Note that on both row 1 and row 2 we have used the number 5 already. 4- only has two possibilities for a 6x6 KenKen puzzle, 6-2 and 5-1. Hence if 5 cannot go in either of the cells in the cage then it cannot be 5-1, leaving 6-2. Let's fill these in:




So now we have an interesting pattern. the 12x cage is a L-shaped figure. This actually provides useful information that you may not first realise. By filling in the 6 on the 2nd row, we know for certainty that the remainder of the 2nd row is numbers 2,3. Hence we can automatically deduce the 3rd row/3rd column cell to be 2 as shown above. Again, there are multiple ways to view this. We can view 12x as a cage and note that we have 2,3 inside the cage already. This leaves us the unique number remaining to be 2 (12 / (2*3)).

For any L-shaped cage, if there are a repeated element (in this case the number 2), then they will always go on the ends of the L-shape. The reason for this is simple, if they were placed any other way they would conflict and violate the unique number rule. Filling in these numbers yields the following partially complete puzzle:



There is another tip that is useful. If you look at the 4th column in which we have filled in (1,5,3,6). We can actually uniquely and correctly identify the 4th number in the first row by noting that we reduced 24x to 1*4*6. But 2 of these numbers have already been used in the 4th column, hence the missing and correct number to fill in is '4'. This gives the partially solved puzzle:



Give it a try to solve the remainder of the puzzle! Happy Solving! =)

[Spoilers Ahead]
Note:
If you get stuck, I've included the solution below:

2 comments: