# How to solve 5x5 grid with 16 diagonals?

I have a grid 5x5 and I have to fill 16 little squares with a diagonal

Rules

• You cannot place more than 1 diagonal in each square
• The diagonals cannot touch each other (example bellow)

But what I seek here is a mathematical solution for this puzzle, I don't even know where to start looking for information.

Can someone explain how do I solve this puzzle using equations?

-

Think of it this way: You have a 5x5 array, and you need to fill it with values 0, 1, or -1, with three restrictions:

1. The cells sharing an edge with a cell with a $\pm 1$ cannot contain a $\mp 1$.
2. If a cell contains a 1, the adjacent cells to the top-left and bottom-right cannot also contain a 1.
3. If a cell contains a -1, the adjacent cells to the bottom-left and top-right cannot also contain a -1.

Here, cells containing a "1" have a diagonal running top-left to bottom-right, and cells containing a "-1" have a diagonal running the other way. Cells containing 0 do not have a diagonal at all.

So, for the example grid you provide, you start with the grid:

$$\begin{matrix}0&0&-1&0&0\\0&-1&0&-1&1\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{matrix}$$

I don't think there's "a mathematical solution" to it - that is, I doubt that one could immediately find the "right answer" without some level of trial and error. But it does give a good starting point to automating the search, if you want to try solving it computationally.

-
Maybe the $+1$ cells should be those whose diagonal slope is positive (from lower left to upper right). That is only a suggestion since positive slope diagonals would be naturally associated to a positve number. But the restatement of the problem is nice, +1. – coffeemath Mar 24 '13 at 8:54

I have written a brute force search, which seems to work. But it would take days to inspect the $3^{25} = 847,288,609,443$ configurations or reimplementation of some parts in C.

Some feasible solutions from a random walk:

[ 45.33%] [1100201102001021010210022]  found: len = 14 [max = 14]

/ / . . \
. / / . \
. . / . \
/ . / . \
/ . . \ \

[ 41.74%] [1020210202102021101001001]  found: len = 14 [max = 14]

/ . \ . \
/ . \ . \
/ . \ . \
/ / . / .
. / . . /

[ 99.59%] [2222200000102011000011111]  found: len = 14 [max = 14]

\ \ \ \ \
. . . . .
/ . \ . /
/ . . . .
/ / / / /

[ 38.82%] [1011110001111010000011111]  found: len = 15 [max = 15]

/ . / / /
/ . . . /
/ / / . /
. . . . .
/ / / / /

-
I think there are only 95 possible patterns for any given row, as $1$ and $-1$ can't be adjacent. That reduces the search space to $95^5=7.7$ billion, or just one percent of the starting point. – Michael Oct 27 '15 at 10:03
Build a $95\times95$ table that shows which rows may be adjacent to which other rows. That replaces repeated comparisons with a lookup. – Michael Oct 27 '15 at 10:10
Sounds good. The idea might be used for the columns as well, should be the same table. – mvw Oct 27 '15 at 10:16

Between two adjacent rows of squares is a row of six corners. Each diagonal uses up one of them, so at most six diagonals in two adjacent rows.
At most six diagonals in rows 1-2, six in rows 3-4, so at least four in row 5 to make sixteen. In the same way, rows 3 and 1 have at least four diagonals.
So rows 2 and 4 have at most two diagonals, or else you get more than six in two adjacent rows.

Seventeen is impossible: Since Row1+Row2 has at most six diagonals, and so does Row3+Row4, you need five diagonals in Row5. For the same reason, you need five in Row3 and Row1. But then you need one in either Row2 or Row4, and the only free corners do not allow a diagonal to join them.

Row3 can't have five diagonals: If it did, Row2 and Row4 could have only one each. That makes seven, leaving nine more between Row1 and Row5. So Row1 or Row5 has five as well. But, just as for the 'seventeen' case, if Row1 and Row3 both have five then Row2 must be empty; so Row4 and Row5 have six between them to make sixteen; So Row5 has five diagonals; so Row4 is empty; and we only have fifteen diagonals.

So Row3 has at most 4. Row1 and Row2 have at most six between them, and so do Row4 and Row5. So to make sixteen total, Row1 and Row2 have exactly six between them, as do Row4 and Row5. There are no spare corners between Row1 and Row2, nor between Row4 and Row5. So, once Row1 is chosen, there are at most four choices for Row2; and similar for Row5 and Row4.

There are 18 possible Row1s with at least four diagonals. There are 16 possible Row3s with exactly four diagonals.

Take the 18 possible Row1s, pair each with its possible Row2 to get a few dozen Row1Row2 pairs. For each pair, check which of the sixteen possible Row3s fits with the particular Row2. Having gone through all Row1Row2 pairs, you have a subset of the sixteen which can be part of a Row1RowRow3 triple.
To check whether that Row3 can attach to a Row4 and Row5, you just have to mirror-reflect it so that rising diagonals become falling diagonals, and check whether that reflection can be part of a Row1Row2Row3 triple.

This is a few hundred comparisons, that might take ten minutes by hand.

-