Joe Maller.com

Solving a difficult KenKen puzzle

That right there is the hardest KenKen puzzle I’ve ever come across. Maybe I’m just missing a strategy and there’s something obvious I overlooked, but I found the levels of ambiguity in this one to be very, very difficult to unravel. I’ve been coming back to this puzzle for months. Having finally cracked it, I wanted to document the solution. Partly to remember what happened, but mostly because it just felt so darn good to finally figure out.

With KenKen puzzles, there is no guessing. The puzzles are logical, and after doing hundreds of them over the past several years, I’ve only come across one or two that seemed to have equally forked possiibilities. And I hated those.

KenKen is similar to Sudoku, rows and columns contain n-digits with no repeats (a Latin Square). With KenKen, it can be helpful to know the sum of all digits in the puzzle’s dimension since every row and column must add up to that Triangular number. For a six digit puzzle this is 21. For this particular puzzle, it’s also worth remembering that there are only three paths to 11: {1, 4, 6}, {2, 3, 6} and {2, 4, 5}. Note the digits unique to each pathway.

Starting Out

The key to breaking into this one was column 6. Since column 6’s top cage sums to 11, and F6 is 5, the sum of D6 and E6 must equal 5. Since the only possibilities are combinations of 1, 2, 3 and 4, and E6 can’t be 1 because the sum of E5 and F5 can’t be 12, there are only three possibilities, D6: {1, 2, 3} and E6: {2, 3, 4}. Since the sum of both cages is 20 and we know 5 is accounted for, the sum of C3 through F6 must be 15. That means A5 and B5 have to add up to 6. The remaining half of that cage, B4 and C4 must add up to 7.

We now know the sum of B4 through F6, so A4 must be 3. This also reveals F3 is also 3 because the sums of all cells in the top two cages of column 3 are known.

Having a 3 in F3 means the remaining slots of that cage, F1 and F2 can only be 2 and 4. This means F4 must be 1 and F5 must be 6 because, like E6, F5 can’t be 1. Additionally, D4 and E4 must contain 4 and 6 because there’s no other way to get to 11 using a 1. The last two cells of column 4 can only be 2 and 5.

The upper left cage, A2, B1 and B2, has limited choices. Since the largest possible number is 6, the sum of any two adjacent sides can’t be less than 9. Likewise, since the largest adjacent sum is 11, neither A2 or B1 can be less than 4. The only exception is B2 which could be 3 since both adjacent cells could be 6.

But the D2, E2 cage can’t contain 3 and 4. If it did, then A2 and B2 could only be 5 and 6, which would mean B1 would have to be 4. The problem is that F1 and F2 can only be 2 or 4 and column 2’s 4 would already be taken by the 3 and 4 in D2 and E2. So, the D2, E2 cage can only be a combination of 2 and 5 or 1 and 6, the sum of A2, B2 must be 9 and B1 has to be 6.

At this point, things get hairy. I couldn’t see any obvious connection and essentially started trying alternate solutions.

A dead end

There are only two remaining combinations for reaching 11 in the A6, B6, C6 cage, but if A2 was 6 and B2 was 3, the only remaining combination would be {1, 4, 6} because the top row would already have 6, 1, and 3, leaving only a 2 or 4 as candidates in A6 except the 2 would be taken by any combination of A3, B3, B4, A5 and B5. So, from here, the top row could only be filled out one way:

That cascades down to E6. Now the D2, E2 cage has would have to be 2 or 5 because the 6 was taken by A2. But E6 couldn’t be 2 because then E5 would have to be 5 which would make E2 impossible. And here’s where this tangent falls apart all over the board. That was a long way to go to prove that A2 and B2 have to be 4 and 5.

It all comes together

Disproving that was painful, but now we’re starting to get somewhere. Confirming A2‘s and B2‘s candidates reveals C2 is 3, F2 is 2 and F1 is 4. This also limits C1‘s candidates to 2 and 5. C4 is also limited to 2 and 5, so no other cells in row C can contain a 2 or 5.

Even better, there’s now only one way to fill in the top two rows:

That pretty much gives it all away. Columns 2, 4 and 6 are quickly revealed and the remaining values are easily discovered.

The solved puzzle:

Solvers

It was interesting and humbling to run this puzzle through two KenKen solvers after finishing it by hand.

Michael Heyeck’s NekNek solver solved the puzzle instantly. Michael documented the creation of his KenKen solver, including the complete python source code (less than 150 lines with comments).

Below is the puzzle in JSON notation for the Poison Meatball solver. It was slightly reassuring that this took a few seconds to get to the answer.

{
    "width": 6,
    "height": 6,
    "values": [1, 2, 3, 4, 5, 6],
    "rules": [{
        "op": "=",
        "value": 1,
        "cells": [{"x": 0, "y": 0 }]
    }, {
        "op": "+",
        "value": 15,
        "cells": [{"x": 1, "y": 0 }, {"x": 0, "y": 1 }, {"x": 1, "y": 1 }]
    }, {
        "op": "+",
        "value": 10,
        "cells": [{"x": 2, "y": 0 }, {"x": 3, "y": 0 }, {"x": 2, "y": 1 }]
    }, {
        "op": "+",
        "value": 13,
        "cells": [{"x": 4, "y": 0 }, {"x": 3, "y": 1 }, {"x": 4, "y": 1 }, {"x": 3, "y": 2 }]
    }, {
        "op": "+",
        "value": 11,
        "cells": [{"x": 5, "y": 0 }, {"x": 5, "y": 1 }, {"x": 5, "y": 2 }]
    }, {
        "op": "+",
        "value": 13,
        "cells": [{"x": 0, "y": 2 }, {"x": 1, "y": 2 }, {"x": 0, "y": 3 }, {"x": 0, "y": 4 }]
    }, {
        "op": "+",
        "value": 11,
        "cells": [{"x": 2, "y": 2 }, {"x": 2, "y": 3 }, {"x": 2, "y": 4 }]
    }, {
        "op": "+",
        "value": 7,
        "cells": [{"x": 4, "y": 2 }, {"x": 4, "y": 3 }, {"x": 5, "y": 3 }]
    }, {
        "op": "+",
        "value": 7,
        "cells": [{"x": 1, "y": 3 }, {"x": 1, "y": 4 }]
    }, {
        "op": "+",
        "value": 11,
        "cells": [{"x": 3, "y": 3 }, {"x": 3, "y": 4 }, {"x": 3, "y": 5 }]
    }, {
        "op": "+",
        "value": 13,
        "cells": [{"x": 4, "y": 4 }, {"x": 5, "y": 4 }, {"x": 4, "y": 5 }]
    }, {
        "op": "+",
        "value": 9,
        "cells": [{"x": 0, "y": 5}, {"x": 1, "y": 5}, {"x": 2, "y": 5}]
    }, {
        "op": "=",
        "value": 5,
        "cells": [{"x": 5, "y": 5}]
    }]
}

Whose Fish? (logic puzzle)

Yesterday I stumbled across this logic puzzle.

What always drives me crazy about stuff like this is that no one ever discusses the answer. I’ve never liked the implied wink wink smarty-pants attitude (see here). I want to know how someone arrives at the answer. What fascinates me is thinking, not trivia or secrets.

Here’s how I found the answer.

I don’t recall ever seeing this puzzle before and did not google it until I’d proven the results to myself. The puzzle is difficult, but I’ve posted answer at the end of the post, so you’ve been warned. The three little dots (∴) is the “therefore” symbol.

First I set up a 6×5 matrix of attributes then started highlighting and crossing out relevant details.

Then I got stuck.

Intuitively, I knew it all came down the Norwegian. This because we know he has only one neighbor. Everyone else can have one or two neighbors. Eventually, it came down to coffee (consumed and in clue 5).

The Puzzle:

There are five houses in a row in different colors. In each house lives a person with a different nationality. The five owners drink a different drink, smoke a different brand of cigar and keep a different pet, one of which is a Walleye Pike.

Who owns the fish?

The 15 clues:

  1. The Brit lives in the red house.
  2. The Swede keeps dogs as pets.
  3. The Dane drinks tea.
  4. The green house is on the left of the white house.
  5. The green house owner drinks coffee.
  6. The person who smokes Pall Malls keeps birds.
  7. The owner of the yellow house smokes Dunhills.
  8. The man living in the house right in the center drinks milk.
  9. The man who smokes Blends lives next to the one who keeps cats.
  10. The Norwegian lives in the first house.
  11. The man who keeps horses lives next to the one who smokes Dunhills.
  12. The owner who smokes Bluemasters drinks beer.
  13. The German smokes Princes.
  14. The Norwegian lives next to the blue house.
  15. The man who smokes Blends has a neighbor who drinks water.

The end of this puzzle will have five units, each with 6 attributes: {address, house color, nationality, drink, pet and smokes}

The data seems to break down into two types: Definitive data, that which defines an attribute directly within one unit. And relational data, which defines an attribute relative to another unit. Relational data often acts as a negating definition as well, showing what isn’t in a unit by describing what’s nearby.

Now stepping through the clues, definitive data related to nationality first:

1. The Brit lives in the red house.
Brit == red
2. The Swede keeps dogs as pets.
Swede == dogs
3. The Dane drinks tea.
Dane == tea
10. The Norwegian lives in the first house.
Norwegian == 1st house
13. The German smokes Princes.
German == Princes

Next comes the secondary definitions. These can be used to reveal data which eliminates possible units based on what is already known:

5. The green house owner drinks coffee.
Coffee == Green ∴
Brit != coffee
Dane != Green
6. The person who smokes Pall Malls keeps birds.
Pall Malls == birds ∴
German != birds
Swede != Pall Malls
7. The owner of the yellow house smokes Dunhills.
Yellow == Dunhills ∴
German != Yellow
Brit != dunhills
8. The man living in the house right in the center drinks milk.
Milk == 3rd House ∴
Norwegian != milk
Dane != 3rd House
12. The owner who smokes Bluemasters drinks beer.
Bluemasters = beer ∴
German != beer
Dane != Bluemasters
First Second Third Fourth Fifth
Blue Green Red White Yellow
Brit Dane German Norwegian Swede
Beer Coffee Milk Tea Water
Birds Cats Dogs Fish Horses
Blends Bluemasters Dunhills Pall Malls Princes
First Second Third Fourth Fifth
Blue Green Red White Yellow
Brit Dane German Norwegian Swede
Beer Coffee Milk Tea Water
Birds Cats Dogs Fish Horses
Blends Bluemasters Dunhills Pall Malls Princes
First Second Third Fourth Fifth
Blue Green Red White Yellow
Brit Dane German Norwegian Swede
Beer Coffee Milk Tea Water
Birds Cats Dogs Fish Horses
Blends Bluemasters Dunhills Pall Malls Princes
First Second Third Fourth Fifth
Blue Green Red White Yellow
Brit Dane German Norwegian Swede
Beer Coffee Milk Tea Water
Birds Cats Dogs Fish Horses
Blends Bluemasters Dunhills Pall Malls Princes
First Second Third Fourth Fifth
Blue Green Red White Yellow
Brit Dane German Norwegian Swede
Beer Coffee Milk Tea Water
Birds Cats Dogs Fish Horses
Blends Bluemasters Dunhills Pall Malls Princes

Many of the relational data clues reveal additional information about what a unit doesn’t have:

4. The green house is on the left of the white house.
Green = White’s address – 1
9. The man who smokes Blends lives next to the one who keeps cats.
Blends = Cat’s address ± 1 ∴
Blends != cats
11. The man who keeps horses lives next to the one who smokes Dunhills.
Horses = Dunhills’ address ± 1 ∴
Dunhills != horses
Horses != Yellow
14. The Norwegian lives next to the blue house.
Blue = 2nd house ∴
Brit != 2nd house
Norwegian != Blue
15. The man who smokes Blends has a neighbor who drinks water.
Blends = Water’s address ± 1 ∴
Blends != water

The fourteenth clue is one of the most important. Since we know the Norwegian lives in the 1st house (clue 10), we know that the blue house is number 2. Number 4 is a tricky one, there is no reason to believe that the green house is the first house, all we know is that the white house is on it’s left. Also, clues 9 and 15 could be referring to one or two neighbors.

It’s interesting that the clues sort out into three quintuplets.

Here’s where it starts to get really hard. All that is known for certain is what was defined in questions 1-3, 10 and 13. There remain three or four unknowns for each unit. What I’m looking for is the first link in a causality chain. Of course it’s probably not so much a chain as a loop, so looking for an end is futile. How about an onramp?

After several minutes of staring, and re-reading the clues, I got the chills (really!)

WARNING: THE ANSWER IS REVEALED BELOW

The green house drinks coffee. The center house drinks milk. So the center house is not green. But the Green house is on the left of the white house. Since we know the second house is blue, we then know that the first house is not green either. So the only place the green house can be is fourth, making the 5th white. Now is the first yellow, or is the first red?

The elimination steps above provide the answer. We know the Norwegian is in the first house, and the Brit is in the Red house. That means the Brit is in the red house in the middle, drinking milk, and the Norwegian’s house is yellow and he smokes Dunhills.

Whoa, more chills.

At this point, the whole things starts to fall together.

Clue 11 puts horses in the blue house.
Clue 3 means the Dane is not in the green house
Clue 15 puts Blends in the second house, and, with clue 9, water and cats in the first house.
etc. etc.

The Answer

Here’s the final breakdown:

First Second Third Fourth Fifth
Yellow Blue Red Green White
Norwegian Dane Brit German Swede
Water Tea Milk Coffee Beer
Cats Horses Birds FISH Dogs
Dunhills Blends Pall Malls Princes Bluemasters

The German has the fish and drinks coffee in the green house, which is fourth on the block.

That was fun.

I hate puzzles.

Update: Here’s a programmatic solution to “Einstein’s Riddle” and another walkthrough by James Yates.