What type of math should I use for this puzzle?

Question

---

I could use help modeling this puzzle. I'm not looking for a solution but I need help in phrasing the problem mathematically. I need a change in paradigm. My friend asked me for help with this puzzle but frankly, I'm not sure where to begin. I'm thinking maybe of a discrete math or maybe even a linear algebra approach but I've not taken either class in many years and am not sure.

I tried discrete math but the expressions I got were too long to be reasonable. Linear algebra struck me only because it's matrix-based but I couldn't find a way to apply it (with further thought seems very much the wrong tool).

Is there a way to set the problem up so that it can be solved in $O(1)$ time?

I am looking up Sudoku algorithms at the moment and hopefully that'll help. Any suggestions to a posable algorithm or model would be great!

Edit: I know I used a lot of buzz words in my original post. These edits should have fixed some of that. I don’t like the name of the puzzle either but I wanted to be somewhat academic in adding a source. To clarify for @Blitzer I just what to know what type of math to use. I spoke of big O notation because I didn’t know if it was possible to solve in a non-algorithmic manner.

The responses I’ve got have been amazing and incredibly detailed. A big thank you to everyone for perpetuating such a helpful community!

Answer 1

I tried to consider it as an Integer Linear Program. We have the binary variables $c_{ij}, d_{ij}, s_{ij}, t_{ij}, e_{ij}$ for $(i,j) \in [6]^2$ indicating (respectively) whether there is a circle, diamond, square, triangle or empty in the place $(i,j)$. Then we have many constraints:

• each place is unique: $\sum_v v_{ij} = 1$
• rows have 1 of each symbol and two empty: $\sum_{j} v_{ij} = \begin{cases} 1, v\neq e \\ 2, v=e \end{cases}$
• similarly for columns

Then for the black arrow constraints. Symbol $v$ with black arrow: then the row (or column and either could be reversed, have to index them accordingly) can't begin $y, ey $ or $eey$ for any other symbol $y$. These can be encoded as

• $y_{i1} = 0$
• $e_{i1}+y_{i2} \le 1$
• $e_{i1}+e_{i2}+y_{i3} \le 2$

The white arrows are even more tricky. Now it can't begin with any of $yz, yez, yeez, eyz, eyez, eeyz$ for any other two symbols $y, z$. And also, because $v$ can't be the first, it can't begin with $v, ev, eev$. These turn to constraints similarly as before.

The program doesn't have an objective function, we're just looking for any feasible solution.

I tried to code this with Sage (my code here). But it says there are no feasible solutions. What mistake did I make, or is this whole idea flawed?

Now with solver='ppl' it doesn't crash but neither does it finish any time soon. Maybe this method without better algorithms isn't any good.

EDIT: I know you're not looking for solutions, but since that Integer program didn't work, I solved it in a usual way. I might as well put it here in the answer. A simple recursive backtracker solves it pretty fast. I made it so that it puts in a whole row at a time (there are $360$ possibilities). Here's the code.

The solution is ($0=$ empty, $1=$ circle, $2=$ diamond, $3=$ square, $4=$ triangle):

\begin{array}{rrrrrr} 4 & 1 & 0 & 3 & 2 & 0 \\ 3 & 2 & 1 & 0 & 0 & 4 \\ 2 & 0 & 0 & 4 & 1 & 3 \\ 1 & 3 & 2 & 0 & 4 & 0 \\ 0 & 0 & 4 & 1 & 3 & 2 \\ 0 & 4 & 3 & 2 & 0 & 1 \end{array}

Answer 2

Here's a correct binary linear programming formulation. For $(i,j)\in [6] \times [6]$ and $k\in \{C, D, S, T\}$, let binary decision variable $x_{i,j,k}$ indicate whether cell $(i,j)$ contains shape $k$. The easy constraints are: \begin{align} \sum_k x_{i,j,k} &\le 1 &&\text{for all $i,j$} \tag1\label1 \\ \sum_j x_{i,j,k} &= 1 &&\text{for all $i$ and $k$} \tag2\label2 \\ \sum_i x_{i,j,k} &= 1 &&\text{for all $j$ and $k$} \tag3\label3 \\ \end{align} Constraint \eqref{1} enforces at most one shape per cell. Constraint \eqref{2} enforces the correct count per row and shape. Constraint \eqref{3} enforces the correct count per column and shape.

Next we enforce the black arrows. For example, consider the black arrow at the top of column $j=1$ with $k=T$. The desired logical implication is $x_{i,j,k} = 1 \implies x_{i_2,j,k_2} = 0$ for all $i$, $i_2 < i$, and $k_2$, which can be enforced via linear "conflict" constraints: $$x_{i,j,k} + x_{i_2,j,k_2} \le 1 \quad \text{for $j=1$, $k=T$, all $i$, $i_2 < i$, and $k_2$}$$ For the black arrow at the right of row $i=1$ with $k=D$, the corresponding constraints are $$x_{i,j,k} + x_{i,j_2,k_2} \le 1 \quad \text{for $i=1$, $k=D$, all $j$, $j_2 > j$, and $k_2$}$$ The other black arrow constraints are similar.

Next we enforce the white arrows. For example, consider the white arrow at the top of column $j=2$ with $k=D$. The desired logical implication is $x_{i,j,k} = 1 \implies \sum_{i_2 < i} \sum_{k_2} x_{i_2,j,k_2} = 1$ for all $i$, which can be enforced via linear "big-M" constraints: $$x_{i,j,k} \le \sum_{i_2 < i} \sum_{k_2} x_{i_2,j,k_2} \le 1+M(1- x_{i,j,k}) \quad \text{for $j=2$, $k=D$, and all $i$}$$ The other white arrow constraints are similar.

The resulting feasible solution turns out to be unique:

  1 2 3 4 5 6 
1 T C   S D   
2 S D C     T 
3 D     T C S 
4 C S D   T   
5     T C S D 
6   T S D   C 

Answer 3

A problem like this is expected to be solved by hand without invoking linear programming or a computer. You are expected to think about what the clues are telling you. In this case, a clue with a black arrow means that symbol must be in the first three spaces in that direction because there are only two blanks per row. The triangle in the first column must therefore be in one of the first three rows, so the triangle in the bottom row cannot be in the first column. The bottom left square is therefore blank. The triangle in the first column cannot be in the third row, so it must be in the first or second. A clue with a white arrow must be in the second, third, or fourth space in that direction. It is very attractive to assume a diamond is in the first row, fifth column. Keep working like this and see where it takes you. It might help to make a grid in a spreadsheet with $0,1,2,3,4$ in each cell representing possibilities, then cross off ones you eliminate. It can help find unique possibilities. The type of math is elementary logic.