Number Puzzle

For example, consider the following number puzzle:

In this puzzle, each row contains two numbers with an inequality symbol between them. The players must use logical deduction and mathematical reasoning to determine the correct values for each number and fill in the grid.

To solve this puzzle, we can start by looking at the third row, which tells us that 5 is greater than or equal to 4. This means that the value in the first column must be either 4 or 5. Next, we can look at the fourth row, which tells us that 8 is less than or equal to 9. This means that the value in the second column must be either 8 or 9.

Now, we can look at the first row, which tells us that 4 is greater than 2. This means that the value in the first column must be 4, and the value in the second column must be 2. Finally, we can look at the second row, which tells us that 7 is less than 9. This means that the value in the first column must be 7, and the value in the second column must be 9.

So, the completed grid looks like this:

Number puzzle inequalities equations are often used in puzzle games, where players are presented with a series of these puzzles that increase in difficulty. By solving these puzzles, players can develop their problem-solving skills and promote critical thinking.

Consider the following puzzle: Choose numbers 1 to 5 such that in the diagram below each number is contained exactly once in each row and each column. The numbers in the fields should respect any inequality between two fields.

making equations

As decision variables we use 𝑥𝑟,𝑐,𝑘 such that 𝑥𝑟,𝑐,𝑘=1 if 𝑘 appears in the field with row 𝑟 and column 𝑐.

The objective is trivial, as there is nothing to optimize. We only need to find a feasible solution.

There should be precisely one value in each field:

∑𝑘=1𝑁𝑥𝑟,𝑐,𝑘=1 for 𝑟=1,…,𝑁 and 𝑐=1,…𝑁.

Each value must be used exactly once in each row:

∑𝑐=1𝑁𝑥𝑟,𝑐,𝑘=1 for 𝑟=1,…,𝑁 and 𝑘=1,…𝑁.

Each value must be used exactly once in each column:

∑𝑟=1𝑁𝑥𝑟,𝑐,𝑘=1 for 𝑐=1,…,𝑁 and 𝑘=1,…𝑁.

Formulating the inequality constraints requires a bit more work. Lets consider an example. In the problem diagram above we see that the value of field 2,1 must be larger than the value in field 1,1. Thus, if field 2,1 has value 3, then field 1,1 is not allowed to have a value of 3, 4, or 5. As a consequence, if 𝑥2,1,3=1, then ∑5𝑤=3𝑥1,1,𝑤=0. More generally, we want that

𝑥2,1,𝑘=1⇒∑𝑤=𝑘5𝑥1,1,𝑤=0.

We can implement this implication with the big 𝑀 trick. Choose some big 𝑀, then set

∑𝑤=𝑘5𝑥1,1,𝑤≤𝑀(1−𝑥2,1,𝑘),

so that if 𝑥2,1,𝑘=1, then ∑5𝑤=𝑘𝑥1,1,𝑤 must be zero, while if 𝑥2,1,𝑘=0, the sum ∑5𝑤=𝑘𝑥1,1,𝑤 is, in practice, unconstrained.

The starting numbers that appear in the diagram above form a simple set of constraints:

𝑥1,5,4=1,𝑥4,1,4=1,𝑥4,5,2=1.

Example codes

param N;             # number of rows = number of columns
param M;             # large enough constant

set R := 1 .. N;

set INEQ, within R cross R cross R cross R;  
set FIX, within R cross R cross R;

var x{R, R, R} >= 0, <= 1, binary;

# There should be precisely one value in each field.
subject to values{r in R, c in R}:
  sum{k in R} x[r, c, k] = 1;

# There should be only one value per row  
subject to rows{r in R, k in R}:
  sum{c in R} x[r, c, k] = 1;

# There should be only one value per column
subject to columns{k in R, c in R}:
  sum{r in R} x[r, c, k] = 1;

subject to ineqConstr{(r1, c1, r2, c2) in INEQ, k in R}:
  sum{w in k..N} x[r1, c1, w] <= M * (1 - x[r2, c2, k]);

subject to fixConstr{(r, c, k) in FIX}:
  x[r, c, k] = 1;
  
solve;

printf "The following is a solution to the puzzle:n";
for {r in R} {
  for {c in R} {
    for {k in R : x[r, c, k] == 1} {
      printf "%2d", k;
    }
  }
  printf "n";
}

data;

param N := 5;
param M := 100;

# Set of quadruples (r1, c1, r2, c2) specifying inequalities among the entries,
# specifying that the entry is row r1, column c1 should be less than the entry
# in row r2, column r2.
set INEQ := (1, 1, 2, 1) (1, 5, 1, 4) (2, 5, 1, 5) (4, 4, 3, 4)
         (4, 1, 5, 1) (4, 3, 4, 4) (4, 5, 4, 4) (5, 5, 4, 5);

# Set of triples (r, c, k) specifying that the entry in row r, column k should
# be equal to k.
set FIX := (1, 5, 4) (4, 1, 4) (4, 5, 2);

end;