Logic Puzzle Solution Part 3: Counting the Possible Configurations

This post is a followup to the Five-House Logic Problem.  I described how I worked out the solution by hand in an earlier post (warning: contains spoilers).  This post is Part 3 of my Microsoft Access solution (see Part 1 here and Part 2 here).

First off, let me begin by apologizing to those of you who were following this series in real time.

It's been almost two months since my last article on this topic.  The humbling reason?  I was stumped.

After writing and testing my oNeighborhood class module, the next logical step in my brute force approach to solving this problem was to test every possible combination of options.  

I thought this would be simple.

With smug satisfaction, I whipped up the following code, hit F5, and waited for the immediate window message–The following neighborhood satisfies the riddle:–that would declare my success.

Sub BruteForce()
    Dim Counter As Long

    Dim Owner As Byte, Pet As Byte, Color As Byte
    Dim Drink As Byte, Flower As Byte, Position As Byte
    
    For Owner = 1 To 5
        For Pet = 1 To 5
            For Color = 1 To 5
                For Drink = 1 To 5
                    For Flower = 1 To 5
                        For Position = 1 To 5
                        Counter = Counter + 1
                            With New ONeighborhood
                                Dim i As Byte
                                For i = 1 To 5
                                    .SetOwner ((Position + i) Mod 5) + 1, ((Owner + i) Mod 5) + 1
                                    .SetPet ((Position + i) Mod 5) + 1, ((Pet + i) Mod 5) + 1
                                    .SetColor ((Position + i) Mod 5) + 1, ((Color + i) Mod 5) + 1
                                    .SetDrink ((Position + i) Mod 5) + 1, ((Drink + i) Mod 5) + 1
                                    .SetFlower ((Position + i) Mod 5) + 1, ((Flower + i) Mod 5) + 1
                                Next i
                                If .SatisfiesRiddle Then
                                    Debug.Print "The following neighborhood satisfies the riddle:"
                                    Debug.Print .NeighborhoodDescription
                                    Stop
                                End If
    
                            End With
                        Next Position
                    Next Flower
                Next Drink
                Debug.Print ".";: DoEvents
            Next Color
        Next Pet
    Next Owner
    Debug.Print Counter & " configurations tested"
End Sub

Instead, I got this:

No configuration that satisfied the riddle, despite the fact that I had tested 15,625 configurations.  What the heck?!?!

An Overly Simplistic Approach

To figure out what was going on, I added the following line of code directly before the If .SatisfiesRiddle Then line:

Debug.Print .NeighborhoodDescription & vbNewLine

I then ran the code for six iterations of the above Debug.Print statement.  Here was the output:

House 1: The English person lives in the red house.  This person drinks coffee, has a dog, and grows geraniums.
House 2: The Spaniard lives in the green house.  This person drinks tea, has snails, and grows roses.
House 3: The Ukrainian lives in the ivory house.  This person drinks milk, has a fox, and grows marigolds.
House 4: The Norwegian lives in the yellow house.  This person drinks orange juice, has a horse, and grows lilies.
House 5: The Japanese person lives in the blue house.  This person drinks water, has a zebra, and grows gardenias.

House 1: The Japanese person lives in the blue house.  This person drinks water, has a zebra, and grows gardenias.
House 2: The English person lives in the red house.  This person drinks coffee, has a dog, and grows geraniums.
House 3: The Spaniard lives in the green house.  This person drinks tea, has snails, and grows roses.
House 4: The Ukrainian lives in the ivory house.  This person drinks milk, has a fox, and grows marigolds.
House 5: The Norwegian lives in the yellow house.  This person drinks orange juice, has a horse, and grows lilies.

House 1: The Norwegian lives in the yellow house.  This person drinks orange juice, has a horse, and grows lilies.
House 2: The Japanese person lives in the blue house.  This person drinks water, has a zebra, and grows gardenias.
House 3: The English person lives in the red house.  This person drinks coffee, has a dog, and grows geraniums.
House 4: The Spaniard lives in the green house.  This person drinks tea, has snails, and grows roses.
House 5: The Ukrainian lives in the ivory house.  This person drinks milk, has a fox, and grows marigolds.

House 1: The Ukrainian lives in the ivory house.  This person drinks milk, has a fox, and grows marigolds.
House 2: The Norwegian lives in the yellow house.  This person drinks orange juice, has a horse, and grows lilies.
House 3: The Japanese person lives in the blue house.  This person drinks water, has a zebra, and grows gardenias.
House 4: The English person lives in the red house.  This person drinks coffee, has a dog, and grows geraniums.
House 5: The Spaniard lives in the green house.  This person drinks tea, has snails, and grows roses.

House 1: The Spaniard lives in the green house.  This person drinks tea, has snails, and grows roses.
House 2: The Ukrainian lives in the ivory house.  This person drinks milk, has a fox, and grows marigolds.
House 3: The Norwegian lives in the yellow house.  This person drinks orange juice, has a horse, and grows lilies.
House 4: The Japanese person lives in the blue house.  This person drinks water, has a zebra, and grows gardenias.
House 5: The English person lives in the red house.  This person drinks coffee, has a dog, and grows geraniums.

House 1: The English person lives in the red house.  This person drinks coffee, has a dog, and grows roses.
House 2: The Spaniard lives in the green house.  This person drinks tea, has snails, and grows marigolds.
House 3: The Ukrainian lives in the ivory house.  This person drinks milk, has a fox, and grows lilies.
House 4: The Norwegian lives in the yellow house.  This person drinks orange juice, has a horse, and grows gardenias.
House 5: The Japanese person lives in the blue house.  This person drinks water, has a zebra, and grows geraniums.

I realized that my initial approach was treating each house individually, rather than taking a holistic view of the entire neighborhood.  The problem was more complex than I appreciated.

Calculating the True Number of Configurations

I honestly wasn't sure how to calculate the total number of configurations that I would need to test.

I tried Googling for the answer and I asked ChatGPT, but neither one got me very far.  ChatGPT went back and forth between telling me I needed to test 120 configurations (i.e., five factorial: 5! = 120) or 15,625 configurations (i.e., five to the sixth power: 5^6 = 15,625).  I knew both numbers were way too low.

Out of ideas, I decided to figure out a formula to calculate the configurations on my own.

Mathematical Discovery via Example

When I'm not exactly sure what formula I should be using to solve a math problem, I will often use one or more simple examples to help me identify a pattern.

In this case, I realized that there are two key inputs that we need to produce our desired output:

• Input 1: Number of variables
• Input 2: Number of options per variable
• Output: Number of unique configurations

I used Excel to help me format the configurations.

2 Variables + 2 Choices Each = 4 Configurations

2 Variables + 3 Choices Each = 6 Configurations

2 Variables + 4 Choices Each = 24 Configurations

3 Variables + 2 Choices Each = 4 Configurations

3 Variables + 3 Choices Each = 36 Configurations

A Formula to Calculate Configurations

Based on these examples–and going through the exercise of building each set of sample configurations–I discovered a formula for calculating the number of unique configurations for a given set of variables (assuming they each have the same number of possible choices).

Here's the formula:

v: Number of variables
c: Number of choices per variable

(c!) ^ (v - 1)

In other words, calculate the factorial of the number of choices per variable, then raise that to the power of the number of variables minus one.

Here are some examples:

v: 2   c: 2   (2!) ^ (2-1) =  2 ^ 1 =  2
v: 2   c: 3   (3!) ^ (2-1) =  6 ^ 1 =  6
v: 2   c: 4   (4!) ^ (2-1) = 24 ^ 1 = 24
v: 3   c: 2   (2!) ^ (3-1) =  2 ^ 2 =  4
v: 3   c: 3   (3!) ^ (3-1) =  6 ^ 6 = 36

The Five House Logic Problem: A LOT of Possible Configurations

The five house logic problem involves 6 variables with 5 options each.  They are:

1. House number: 1, 2, 3, 4, 5 (5 options)
2. Color: red, green, ivory, yellow, blue (5 options)
3. Nationality: English, Spaniard, Ukrainian, Norwegian, Japanese (5 options)
4. Pet: dog, snails, fox, horse, zebra (5 options)
5. Drink: coffee, tea, milk, orange juice, water (5 options)
6. Flower: geranium, roses, marigolds, lilies, gardenias (5 options)

I created a listing in Excel of all the possible configurations for 2 to 6 variables and 2 to 6 choices per variable.  The corresponding row for the five house logic puzzle is highlighted in yellow.  

Spoiler alert: there are over 268 billion neighborhood configurations!

Brute forcing this thing might be harder than I thought...