Skip to content
Advertisement

How can I solve this arithmetic puzzle? My solution is too slow after n = 14

Given numbers 1 to 3n, construct n equations of the form a + b = c or a x b = c such that each number is used exactly once. For example:

JavaScript

The question is, does a solution exist for every n?

I tried writing a basic program and it becomes too slow after n = 14. Here are the solutions I have so far:

JavaScript

Here’s the code for the program:

JavaScript

Advertisement

Answer

This looks like a combinatorial problem where its “messiness” suggests no mathematical answer can be formulated. The cheer number of allowed combinations makes it ever more likely that each n has a valid solution, especially given that for small n you already found solutions.

Finding solutions for larger n can be tricky. One approach is called “simulated annealing”, where you would take a random set of equations, I try to improve it step by step. “Bad equations” (i.e. equations that have numbers overlapping with others in the set) get removed, and new equations are tried.

Whatever approach is used, it probably can be speed up with heuristics. Such as start creating equations for numbers that show up in the least number of possible equations.

A somewhat related problem is called “graceful labeling”, which has no definite answer and for which similar algorithms are appropriate.

Here is an approach using z3py, a library which implements a sat/smt solver.

First, for each number, a list of possible expressions is made. For each possible expression, a symbolic boolean indicates whether the expression will be used in the solution. To have a valid solution, for each number, exactly one of its possible expressions should be True.

JavaScript
JavaScript
User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement