Does this linear function exist?

Question

I'm trying to solve Sudoku using linear programming. In Sudoku, it is known that each row and column of the grid must contain number from 1 to 9 without duplicates. I need a constraint function that enforces this rule.

Given a set of natural numbers: $a_1, a_2, a_3$. I need a linear function $f$ (ie. $f(a_1, a_2, a_3) = c_1 a_1 + c_2 a_2 + c_3 a_3$) to check whether the set is contains each number starting from 1 in order once. For example, the linear function will return some value $x$ for the following permutations

$f(1,2,3) = x$

$f(2,1,3) = x$

$f(3,1,2) = x$

$f(1,3,2) = x$

$f(2,3,1) = x$

$f(3,2,1) = x$

But will return different value for the other permutations like

$f(1,2,5) ≠ x$

$f(2,2,2) ≠ x$

$f(3,1,-1) ≠ x$

$f(10, 2,-6) ≠ x$

$f(3, 4, 5) ≠ x$

I'm thinking about $f(a_1, a_2, a_3)=a_1+a_2+a_3$ which will return 6 for any permutation of $1,2,3$. But this function will also return the same result $2,2,2$ which is not what I want. Does the better linear function exist?

If the linear function does not exist then what is the nonlinear function for this problem?

Answer 1

Clearly this is not possible with a linear function. This problem can be formulated as

$$Ma=x\mathbf{1}$$

where $a=(a_1,a_2,a_3)$, $\mathbf{1}$ is the vector of ones, $M\in\mathbb{R}^{6\times 3}$ that contains all the permutations of the numbers $(1,2,3)$ vertically, and $x$ is an arbitrary number. Note that $M$ is full column rank.

Then, this underdetermined system of equations and either it has zero solutions or only one solution. In that case, the only solution is

$$a = \dfrac{x}{6}\mathbf{1}.$$

If we set $x=6$, then we recover your solution.

As a result no linear function can do what you are looking for.

Answer 2

A linear function of $3$ variables that satisfies $6$ constraints is going to be trivial unless there are some strong dependencies amongst those constraints. The first $4$ of your constraints are enough to show that your $f$ must be zero everywhere. If $$ f(1, 2, 3) = f(2, 1, 3) = f(3, 1, 2) = f(1, 3, 2) $$ Then:

$$ f(-1, 1, 0) = f((1, 2, 3) - (2, 1, 3)) = f(1, 2, 3) - f(2, 1, 3) = 0\\ f(-2, 1, 1) = f((1, 2, 3) - (3, 1, 2)) = f(1, 2, 3) - f(3, 1, 2) =0 \\ f(0, -1, 1) = f((1, 2, 3) - (1, 3, 2)) = f(1, 2, 3) - f(3, 1, 2) = 0 $$

But {(-1, 1, 0), (-2, 1, 1), (0, -1, 1)} is a basis for $\Bbb{R}^3$ and if $f$ vanishes on a basis it vanishes on the whole of $\Bbb{R}^3$.

For what it's worth (it won't help you with linear programming), for $a_1, a_2, a_3 \in \Bbb{N}$, the quadratic defined by: $$ f(a_1, a_2. a_3) = a_1^2 + a_2^2 + a_3^2 $$ is equal to $14$ iff $\{a_1, a_2, a_3\} = \{ 1, 2, 3\}$.

Answer 3

You can define a plane in 3D space with

$$ax + by + cz = d$$

or by using your variables:

$$c_1 a_1 + c_2 a_2 + c_3 a_3 = x$$

A plan can be fully defined by three points exactly. You can solve for the exact equation by plugging in points and making a system of linear equations and setting $d = 1$ (multiplying $a, b, c,$ and $d$ by any number returns the same equation, so we have a free variable, so we can just set $d$ as 1 so we can solve).

Once you solve for a plane with $d=1$, you can pick $x$ to be literally any value, you just multiply both sides by $x$, and all the same points in that plane go to $x$ now in the function.

For this case though, now you need to check two things:

• Do all your points that you wish to go to $x$ satisfy your equation?
• Do all your points that you wish to not go to $x$ fail to satisfy your equation?

What we know is that either this equation we created works, or no solution exists as any other solution wouldn't include the first three points you picked. So just plug in and check for these. In general a solution won't be found in most cases.

There are an infinite number of nonlinear equations you can come up with to satisfy a properly defined set of mappings (aka no point maps to more than one value). If you want an exact polynomial fit, you can create one for 1D at least with Lagrange polynomials, but that would overfit. You would probably wanna just play around with functions, and get some cross validation going to see if you are overfitting, if you are looking for a machine learning or optimization approach.

A better AI approach is shown here that basically defines a utility function and determines where the best place to put a number and what number to put there is.

If you want to go into theory more though, I would look into Integer Programming, which would be required to solve any sudoku puzzle purely through optimization. Linear Integer programming wouldn't work though given what we've already established

Answer 4

You are asking about the alldifferent polytope. This survey paper by Willem-Jan van Hoeve includes a linear programming formulation (Theorem 19) for $\text{alldifferent}(x_1,\dots,x_n)$, where the variables are $x_i \in \{d_1,\dots, d_n\}$ and the $d_i$ are specified constants such that $d_1 \le \dots \le d_n$. For sudoku, we have $n=9$ and $d_i=i$, and the constraints are \begin{align} \sum_{i=1}^9 x_i &= 45 \\ \sum_{i\in I} x_i &\ge \frac{|I|(|I|+1)}{2} &&\text{for $I \subset \{1,\dots,9\}$} \\ \end{align}