Solving a logical puzzle with programming

Solve the puzzle in a way that each symbol has its unique value. Guess the operation between the symbols in the cells and then add the cells together to get the number on the right and the bottom.

I couple of days ago I got an interesting piece of a logical puzzle from my friend Zoli.

As a person with some mathematical background, I immediately applied everything that I have learned to solve the problem. I started with Gaussian elimination … :-)

After a few tries, I come up with a solution but it was not good (elegant as he said) to my friend. I substituted each symbol pair (see the figure for the puzzle) with its variable and then just figured out one of the possible solutions.

But instead of giving a numeric value for all the 9 symbol pairs he demanded a single value for each symbol.

Fair enough I said and I decided to write a program that can do the calculation for me.

public function runSequence(int $length = 5000): bool {

        $this->set->clear();

        for ($j = 0; $j < $length; $j++) {

            $guess = $this->generateGuess();

            if ($this->evaluateSolution($guess)) {
                $this->printSolution($this->extractGuess($guess));
                return true;
            } else {
                $this->set->add($guess);
            }

        }

        $this->resetVariables();
        return false;

    }

The code is relatively simple:

• it is generating a guess,

• evaluate the guess to check whether it full-fills the puzzle,

• and if it does then prints out the solution,

• if the guess is not a solution then it stores the guess in a set so the next guess will be unique.

Generating a guess involves picking 4 different values from a range of possible values:

public function generateGuess(): array {

    $guess = $this->generateElements();
    while ($this->checkIfGuessExists($guess) || count(array_unique($guess)) !== 4)
       $guess = $this->generateElements();
    return $guess;

}

We keep generating our next guess until it contains 4 unique values (I assumed that the solution will have a different value for each symbol) or until we got a guess that we did not try before.

Generating the vector of random elements is as simple as one can get it.

public function getRandomElement() {
        return $this->range[array_rand($this->range)];
}

public function generateElements(): array {
        return array_map(fn() => $this->getRandomElement(), range(1, 4));
}

Once we have our educated :-) guess we evaluate our solution.

public function evaluateSolution(array $guess): bool {

  return array_reduce([...$this->validateSolution($guess, $this->multiply(...))],
    fn ($validGuess, $eq) => $validGuess && $eq
  , true);

}

Now this method is interesting.

First of all, we reduce the result of our validateSolution method that returns a generator for each equation checked.

Based on the puzzle I have defined 8 different equations using the symbols and then added each cell value to the one on its right or to the one below.

We pass a callable to our validateSolution method. It will use this callable as a function to operate on the symbols in a given cell.

In the example above this is a simple multiplication but you can change it to anything you want.

Then we aggregate the result of each equation (as returned by their relevant generator) in a logical variable. If all equations were true then we have found a solution.

Now, let us take a look at how we validate a solution.

public function validateSolution(array $guess, callable $op) {

        list($a, $b, $c, $d) = $this->extractGuess($guess);

        if ($op($a, $a) + $op($c, $c) + $op($c, $c) + $op($a, $a) == 40) {
            $this->a = $a; $this->c = $c;
            yield true;
        } else {
            yield false;
        }

        if ($op($a, $a) + $op($a, $a) + $op($d, $d) + $op($d, $d) == 26) {
            $this->a = $a; $this->d = $d;
            yield true;
        } else {
            yield false;
        }

        ...

The reason we need to extract our guess is related to the “greediness” of our approach.

If it finds a value for a symbol that makes at least one of the equations true then it fixes its value for later so we only need to find a possible value for the remaining symbols.

So we either use this fixed value or get the value out of our guess for a symbol.

Once we have all symbols set for validation we use our operator function to check every row and column in our puzzle as an equation.

If the symbols are correct for an equation then we generate a true response with PHP’s generator function yield.

If not then we generate a false response.

Nothing fancy here …

If all equations are true then we have guessed the symbol’s values correctly and we print out our solution.

public function printSolution(array $solution): void {
  echo 
    sprintf("We have found a solution: a = %.1f, b = %.1f, c = %.1f, d = %.1f", ...$solution);
}

I have to admit that I enjoyed writing this code — in one of my evenings - almost as much as I enjoyed solving the puzzle in my head.

It is always a good opportunity to throw your programming skills into solving such a problem if you can find some free bandwidth after your daily work.

Spoiler alert!

I copied the final result of the puzzle here … so if you would like to solve it yourself then do not look here :-)

You can find the final version of the code at: https://gist.github.com/dihjital/6c5a7c062cf65d7e761fd09d8318e545

> $z = new Zoli
= App\Graph\Zoli {#3986}

> while(!$z->runSequence(8500)) {}
We have found a solution: a = 2.0, b = 1.0, c = 4.0, d = 3.0