9
$\begingroup$

I found this programming related problem too difficult for me. The problem asks to find 16 integers and form a 4x4 grid

$$\left(\begin{array}{cccc} n_1 & n_2 & n_3 & n_4 \\ n_5 & n_6 & n_7 & n_8 \\ n_9 & n_{10} & n_{11} & n_{12} \\ n_{13} & n_{14} & n_{15} & n_{16} \end{array}\right)$$

That square has 30 subsquares. Can one find a set of those 16 integers such that sums of elements in subsquares contains all integers from 1 to 24?

Note, there are 16 1x1-squares with sum equal to their single numbers; nine 2x2-squares sums of 4 numbers; four 3x3-squares sums of 9 numbers; and one 4x4-squares sum of 16 numbers.

$\endgroup$
  • $\begingroup$ "positive, zero and negative ones": does "ones" mean the integer "1", or it referring to individual integers as "one of the set"? More directly, what integers are allowed? If it's any integer, you can remove the redundant "positive, zero and negative". Otherwise, maybe say something like "integers no less than -1". $\endgroup$ – TheRubberDuck Sep 12 '14 at 12:48
  • $\begingroup$ True. I removed that part as all integers are allowed. $\endgroup$ – squarefan Sep 12 '14 at 12:50
  • $\begingroup$ A meta-puzzle question: is the point of this puzzle to find such a grid, or to write a reasonably clever program to find it? $\endgroup$ – TheRubberDuck Sep 12 '14 at 13:57
  • $\begingroup$ The point is just to find such a grid. $\endgroup$ – squarefan Sep 12 '14 at 14:02
  • $\begingroup$ So for each of the 16 smallest subsqaures is the sum simply the one element that square has. If not then please clarify what you mean by - "sums of elements in subsquares" maybe you could show a picture. $\endgroup$ – Hubble07 Sep 12 '14 at 16:11
8
$\begingroup$

After studying the puzzle I believe that finding a solution by hand would be feasible for a good mathematician with time to spare. I also believe that the number of possible solutions is quite big.

Using a computer program I have found a solution:

-42  22  23   7
 13  11 -32  14
-23  16  15   8
 19   9 -22   1

It has the following square sums:

  4  24  12       3  84      39
 17  10   5       6  20
 21  18   2

My program use simulated annealing, which is somewhat unconventional for a puzzle that asks for an exact solution.

The trick is to find a method of measuring the quality of a solution candidate, along with a method of transforming it into "neighbours" that fit both one another and the concept of simulated annealing in general.

My program measure quality by first sorting the list of all 30 square values, then for each of the 7 sub-lists of length 24 it compares each number to the corresponding solution number, and add the absolute difference to the score for the sub-list, the lowest score of these 7 sub-lists is then the score for the solution candidate, and the lower a candidate scores the closer it is considered to be to a solution.

In each iteration step my program will create new candidates by picking a random selection of the 16 numbers, possibly picking some of them multiple times, and for each pick randomly add either -1, 0 or 1. Thus keeping the change of the quality measure bounded by the number of picks.

My code use numbers 500 greater than the actual solution numbers in order to make sorting a bit simpler, that is just a JavaScript thing. I also skip checking the two first of the 7 sub-lists as I have proven that there must be at least 2 negative numbers in a solution. It is quickly written code, but here goes:

<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="content-type" content="text/html;charset=utf-8">
<title>Integer Grid</title>
</head>
<body>
<script>
var grid=[]
var a,b,c,d
for(a=0;a<30;a++){
    grid[a]=500
}
var scramble
var iterations
var newgrid
var sortgrid
var score
var minscore
var branches
var best
var bestscore
for(scramble=50;scramble>0;scramble--){
    for(iterations=0;iterations<10000;iterations++){
        bestscore=1000000
        for(branches=0;branches<30;branches++){
            newgrid=grid.slice(0)
            for(a=0;a<scramble;a++){
                b=Math.floor(Math.random()*16)
                newgrid[b]+=Math.floor(Math.random()*3)-1
            }
            newgrid[16]=newgrid[0]+newgrid[1]+newgrid[4]+newgrid[5]-1500
            newgrid[17]=newgrid[2]+newgrid[1]+newgrid[6]+newgrid[5]-1500
            newgrid[18]=newgrid[2]+newgrid[3]+newgrid[6]+newgrid[7]-1500
            newgrid[19]=newgrid[8]+newgrid[9]+newgrid[4]+newgrid[5]-1500
            newgrid[20]=newgrid[10]+newgrid[9]+newgrid[6]+newgrid[5]-1500
            newgrid[21]=newgrid[10]+newgrid[11]+newgrid[6]+newgrid[7]-1500
            newgrid[22]=newgrid[8]+newgrid[9]+newgrid[12]+newgrid[13]-1500
            newgrid[23]=newgrid[10]+newgrid[9]+newgrid[14]+newgrid[13]-1500
            newgrid[24]=newgrid[10]+newgrid[11]+newgrid[14]+newgrid[15]-1500
            newgrid[25]=newgrid[16]+newgrid[20]+newgrid[2]-newgrid[5]+newgrid[8]-1000
            newgrid[26]=newgrid[18]+newgrid[20]+newgrid[1]-newgrid[6]+newgrid[11]-1000
            newgrid[27]=newgrid[22]+newgrid[20]+newgrid[4]-newgrid[9]+newgrid[14]-1000
            newgrid[28]=newgrid[24]+newgrid[20]+newgrid[7]-newgrid[10]+newgrid[13]-1000
            newgrid[29]=newgrid[16]+newgrid[18]+newgrid[22]+newgrid[24]-1500
            sortgrid=newgrid.slice(0).sort()
            minscore=1000000
            for(a=2;a<=6;a++){
                score=0
                b=a+24
                for(c=a,d=501;c<b;c++,d++){
                    score+=Math.abs(d-sortgrid[c])
                }
                minscore=Math.min(minscore,score)
            }
            if(minscore<bestscore){
                bestscore=minscore
                best=newgrid
            }
        }
        grid=best
        if(bestscore===0){
            console.log("Solution:")
            console.log(grid)
            throw new Error("Done")
        }
    }
    console.log(grid)
}
</script>
</body>
</html>

0 to 25

I have experimented a bit with extending the puzzle, the best I have is a solution with all the numbers from 0 to 25, but 1 to 26 have eluded me, maybe it is impossible, maybe I just haven't hit it. I expect that it is in general easier to find solutions where the average of the series is closer to 0.

 16  15   8   0      19   1  23      25  18      87
 13 -25   3  12       4 -34  11      14  22
  7   9 -21  17      24  10  21
  6   2  20   5

-7 to 21

30 consecutive numbers is impossible, as the sum of 30 consecutive numbers is always odd, and the sum of the 30 numbers in the puzzle is always even. But 29 consecutive is doable, the highest such series I have found run from -7 to 21:

  9  -4  12  13      15  10  18      17  16      55
  6   4  -2  -5       0   1  -6      20  21
 -7  -3   2  -1       3  14  19
  5   8   7  11

Extreme solutions

Inspired by Florian F's observations about big and small numbers I decided to find some solutions that include really high and really low values, the best i have managed to find is a solution that include the number -99, and one that include 63 in the 16 base numbers:

-99  11   4  13     -60  23  24     -45  16       1
 22   6   2   5      17   3   7      77  15
 14 -25  20 -20      18  12  19
 21   8   9  10

 63   3   1  13      15  20  23      22   9      73
-62  11   5   4     -68   7   8       2  24
 10 -27  18 -19      16  17  19
 21  12  14   6
$\endgroup$
  • $\begingroup$ nice work! ___ +1 $\endgroup$ – Rafe Sep 14 '14 at 14:55
3
$\begingroup$

Damn! too late. I got the following:

-39  23  10 -22
 16 -21   3  11
  7  17   5   1
  9 -20   6  12

My method is to start from a random grid, then adjust individual values to the value that maximizes the score (number of values in 1..24 represented). Usually it blocks at 22, so I just restart until I find a solution. It is slow.

Interestingly, no grid with score 23 or 24 uses a value >24, while some use values as low as -58. I would have expected the values to extend less in the negatives than in the positives.

$\endgroup$
  • $\begingroup$ The majority of the numbers in the grid obviously have to be positive. But the 16 base numbers need to have a relatively low average in order to prevent the square sums from being too large, thus at least a few large negative numbers are needed. Numbers higher than 24 on the other hand do not contribute to the set of required numbers, and in order for the sums they are involved in to be useful, they need some negative neighbours. $\endgroup$ – aaaaaaaaaaaa Sep 14 '14 at 15:20

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.