1
$\begingroup$

Here below is a challenge that circulated on internet.

Complete the Square Grid!

$$\begin{array}{|c|c|c|c|c|}\hline & & & 20 & 21 \\\hline & 6 & 5 & 4 & \\\hline 23 & 7 & 1 & 3 & \\\hline & 9 & 8 & 2 & \\\hline 25 & 24 & & & 22\\\hline \end{array}$$

The integers from 1 to 25 have to placed in the grid so that each number except 1 and 2, is the sum of two of its adjacent cells (in this grid 1 has 8 adjacent cells).

This is fairly trivial given the numbers of inputs already provided. Now, I was told that only having 18 in the centre ensures the unicity of the solution (excepting symmetries and rotations). I dig around on internet and I found the following grid in a programation challenge (unfortunatly no solution has been provided)

$$\begin{array}{|c|c|c|c|c|}\hline & 7 & & & \\\hline & & & & \\\hline & & 18 & & \\\hline & & & & \\\hline & & & & \\\hline \end{array}$$

I have been thinking a lot about it but I can't see any way to tackle this. Out of despair I tried brute force (despite the 13! possibilities that should prevent brute force approach) and obviously it failed. However, after 6 hours of running, heating and before the battery dies I found that no number below 8 can be put on top left position of the grid. Still, it does not bring me far.

If anyone could lead me in the right direction of how to solve this that would be very much appreciated.

$\endgroup$
  • $\begingroup$ I don't understand .. in the original challenge, how is 4 the sum of two of its adjacent cells? They would have to be 1 and 3 .. but 1 is not adjacent to 4 ... I must be misunderstanding something ... Or is it that 1 is adjacent to 3, and 3 is adjacent to 4, and so that makes 1 and 3 as a pair adjacent to 4? $\endgroup$ – Bram28 Apr 30 at 15:33
  • $\begingroup$ @Bram28: I think the idea is that diagonally adjacent counts as adjacent. $\endgroup$ – joriki Apr 30 at 15:40
  • $\begingroup$ @joriki Ah, yes, that's probably it! Not a typical use of 'adjacent' .. I'd call that a 'neighbor' square or one of the 'surrounding' squares maybe? $\endgroup$ – Bram28 Apr 30 at 15:42
  • $\begingroup$ So .. if it took 6 hours to rule out number 1 through 6 in the top left square ... then it should take at most 'only' another 18 hours to get the solution, no? :) $\endgroup$ – Bram28 Apr 30 at 16:05
  • $\begingroup$ Consider to apply Backtracking if you haven't used it yet $\endgroup$ – Tortar Apr 30 at 17:39
1
$\begingroup$

I don't think there is a really clean mathematical path towards the solution: with 8 'adjacent' squares the possibilities very quickly multiply, while at the same time most numbers can be composed of two other numbers in many ways. So, some amount of brute forcing seems unavoidable to me.

Still, some brute forcing methods can be 'smarter' than others. The fact that you say that you figured out the the top left square cannot be on of the umber 1 through 6 suggests to me that you are trying to fill in the grid starting at that very left corner, and working your way down the grid from there, probably row by row ... am I right? If so, I don't think that is a very 'smart' brute force method.

Note that the $3$ needs to be adjacent to the $1$ and the $2$. And the $4$ needs to be adjacent to the $1$ and $3$. For the $5$ you have several options (adjacent to $1$ and $4$ or to $2$ and $3$), but nevertheless you have limited options. So, I would suggest a brute forcing method that takes advantage of those constraints that exist for the 'lower' numbers.

One way is to keep sticking to your 'row by row' filling up of the grid, but to keep a close eye on those lower numbers. Now, you apparently already started with those lower numbers, so that's good. But note: after placing the $1$, the $2$ will have to be close by because of the $3$. That is, after placing the $1$, you can immediately stop exploring any further filling up of the board of you place the $2$ more than $2$ squares away from that $1$. And again, you can also take a close look at the $3$, $4$, $5$, and $6$ to quickly eliminate possibilities before going any further into the 'search tree'. I wouldn't check for the more higher numbers (say, $10$ and up, and maybe even $8$ and up), because the cost of doing that explicit check in your code may be higher than the gain you make in eliminating trees.

Now, maybe you are already doing this in your brute force search. ... but I think there is an even better way to do things:

Instead of filling up the grid one by one, I would approach it differently: I would start with $1$, and consider all possible placements of the $1$ on the board. After placing the $1$, place the $2$. As already pointed out, there are a limited number possibilities for this given the placement of the $1$. Now the $3$: that one will be really limited. Same for the $4$. Etc. If you approach the possibilities this way, I venture that this 'number-by-number' approach will end up exploring a much smaller number of possibilities than with your 'row-by-row' approach. Try it!

Here is my explanation why I believe the 'number-by-number' approach will end up exploring a much smaller number of possibilities than with your 'row-by-row' approach. Let's consider the 'row-by-row' approach.

At some point you get to:

\begin{array}{|c|c|c|c|c|} \hline 4&7&1&2&3 \\ \hline &&&&\\ \hline &&18&&\\ \hline &&&&\\ \hline &&&&\\ \hline \end{array}

At this point you would go back because of the problem with the $3$.

OK, but some time later you get to:

\begin{array}{|c|c|c|c|c|} \hline 5&7&1&2&3 \\ \hline &&&&\\ \hline &&18&&\\ \hline &&&&\\ \hline &&&&\\ \hline \end{array}

And, once again you'd go back because of the $3$. But note you'd be doing this for a whole bunch of other numbers as well. That is: it is the same problem that you're running into several times.

OK, but now consider the 'number-by-number' approach. Here, at some point you get:

\begin{array}{|c|c|c|c|c|} \hline &7&1&2&3 \\ \hline &&&&\\ \hline &&18&&\\ \hline &&&&\\ \hline &&&&\\ \hline \end{array}

And now note: by rejecting this as a valid board, you thereby reject all the earlier boards that would have had the $1$, $2$, and $3$ in that same spot at the same time. So this really should reduce the search space and speed things up.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What you described is exactly what I did starting top left and considering reduced possibilities for low number. This is why I could "quickly" eliminate lot of possibilities for top left number but unfortunately this is also why I can't go further with that method for numbers above 8 (start to have too many branches). I do not understand why the 'number-by-number' approach will end up exploring a much smaller number of possibilities than the row by row approach ... I could try but as I do not understand the logic I might endup doing a bad implementation of it --- $\endgroup$ – akasolace May 1 at 11:05
  • $\begingroup$ @akasolace Yes, I realized that with your aproach ruling out numbers 1 through 6 would take less time than ruling out higher numbers for the top left corner ... so please disregard my remark in the Comments that that would take another 18 hours at most. However, I still believe that the 'number by number' approach should go faster than the 'row-by-row' aproach. I'll try and explain my reasoning a bit later ... $\endgroup$ – Bram28 May 1 at 13:57
  • $\begingroup$ This is indeed the way to go. Optimal code will return the solution in milliseconds. $\endgroup$ – Daniel Mathias May 1 at 20:58
  • $\begingroup$ @DanielMathias Oh! So did you create some code? $\endgroup$ – Bram28 May 1 at 21:33
  • $\begingroup$ Yes, C code. The solution for this is returned instantly. Code to count the total number of distinct grids returns $7102$ in just over 2 seconds. $\endgroup$ – Daniel Mathias May 1 at 23:08
0
$\begingroup$

SPOILER: The completed grid:

$$\begin{array}{|c|c|c|c|c|}\hline 19 & 7 & 9 & 23 & 22 \\ \hline 12 & 5 & 2 & 8 & 14 \\ \hline 13 & 3 & 18 & 6 & 24 \\ \hline 16 & 1 & 4 & 10 & 21 \\ \hline 17 & 20 & 11 & 15 & 25 \\ \hline \end{array}$$

Links to source code:
C code
Python code
(You'll need NumPy for this.)

OnlineGDB has a relatively slow execution time, but the Python code reaches the solution in under five seconds and completes in under eight seconds. The faster online compilers execute the Python code in under one second. The C code, as suggested in my comment, has a reported time of zero seconds, i.e. under ten milliseconds.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ my code finally returned a solution after ... 11 hours ! I will look at your code see what is it that I missed ! $\endgroup$ – akasolace May 3 at 11:52
0
$\begingroup$

You can solve the problem via integer linear programming as follows. Let $N_{i,j}$ be the set of neighbors of cell $(i,j)$. Let binary variable $x_{i,j,k}$ indicate whether cell $(i,j)$ contains values $k$. For $k\in\{3,\dots,n^2\}$ and $s\in\{1,\dots,\lceil k/2\rceil-1\}$, let binary variable $y_{s,k-s}$ indicate whether values $s$ and $k-s$ appear among the neighbors of value $k$. The constraints are: \begin{align} \sum_k x_{i,j,k} &= 1 &&\text{for all $i$ and $j$} \tag1 \\ \sum_{i,j} x_{i,j,k} &= 1 &&\text{for all $k$} \tag2 \\ x_{i,j,k} &= 1 &&\text{for $(i,j,k)\in\{(1,2,7),(3,3,18)\}$} \tag3 \\ \sum_s y_{s,k-s} &\ge 1 &&\text{for $k\in\{3,\dots,n^2\}$} \tag4 \\ x_{i,j,k} + y_{s,k-s} - 1 &\le \sum_{(\bar{i},\bar{j})\in N_{i,j}} x_{\bar{i},\bar{j},s} &&\text{for all $i$, $j$, $k$, and $s$} \tag5\\ x_{i,j,k} + y_{s,k-s} - 1 &\le \sum_{(\bar{i},\bar{j})\in N_{i,j}} x_{\bar{i},\bar{j},k-s} &&\text{for all $i$, $j$, $k$, and $s$} \tag6 \end{align} Constraint $(1)$ assigns one value per cell. Constraint $(2)$ assigns one cell per value. Constraint $(3)$ enforces the fixed values. Constraint $(4)$ assigns a pair of summands for each value. Constraints $(5)$ and $(6)$ force these two summands to appear among the neighbors of the cell $(i,j)$ that is assigned value $k$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.