1
$\begingroup$

I'm developing a solver for a simple constraint-based puzzle game. Here is an example of the puzzle:

$$\begin{align} - \;6\; -\\ - - -\\ - \;3\; - \end{align} $$

The given 3$\times$3 grid of "clues" form constraints on the number of adjacent cells that may be filled with an $x$. The above puzzle has a 3 in the lower middle, indicating that the six neighboring cells must have exactly 3 filled with an $x$. Similar information is given by the 6 clue. Therefore, the solution to the above puzzle is:

$$\begin{align} x\; x\; x\\ x\; x\; x\\ - - - \end{align} $$

Hopefully the idea of the puzzle is clear.

My initial idea was to formulate the given puzzle as a system of equations and solve for $f_{ij} \in \{0,1\}$, where $f_{ij}=1$ if cell $(i, j)$ has an x in the solution.

Let $v_{i\cdot n+j} = f_{ij}$ where $n$ is the width/height of the (square) puzzle. This just linearizes the $f$ dimension. Then the above puzzle can be formulated like this:

$$ \begin{pmatrix} 1~1~1~~~1~1~1~~~0~0~0~\\ 0~0~0~~~1~1~1~~~1~1~1~\\ 0~0~0~~~0~0~0~~~0~0~0~\\ \vdots\\ 0~0~0~~~0~0~0~~~0~0~0 \end{pmatrix} \cdot \begin{pmatrix} v_0 \\ v_1 \\ v_2 \\ \vdots \\ v_8 \end{pmatrix} = \begin{pmatrix} 6 \\ 3 \\ 0 \\ \vdots \\ 0 \end{pmatrix} $$

The problem with this formulation is that the solution to the above system of equations will be parametric. Somehow my formulation isn't capturing all of the information about the puzzle, probably the fact that $v_i \in \{0,1\}$. But I don't know how to change my formulation to include this additional information.

Is there a different way to formulate these puzzles to be able to solve them mathematically?

$\endgroup$
  • $\begingroup$ the first line of $V$ tells you $v_0=\dots =v_5=1$, and find $V^{-1]$ for the others. $\endgroup$ – JonMark Perry Oct 31 '15 at 14:29
  • $\begingroup$ the last column shouldn't have $0$'s in it, use variables for unknowns instead $\endgroup$ – JonMark Perry Oct 31 '15 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.