Squares inside a square

Distribute the digits from 1 to 9 to a 3x3 square, such that you reach as many square numbers as possible. A valid square number in the 3x3 square is either a single digit square number
or is build with neighbouring number(s) either vertically, horizontally or diagonally. Example:

9 8 7

6 5 4

1 3 2


In this example the square numbers are 1, 4, 9, 16, 25, 36, 169, 961 - a total of 8 squares.

Bonus: What is the maximum of squares in a 4x4 square, if using the hexadecimal system with digit 0-9 and A-F? Note, square numbers here are f.e. 10=4*4 or 2A4=1A*1A.

• What are the rules for 'building with neighbouring number(s)'? Would finding a line of 9-1-6 be an acceptable way to build 169 and 961, or do you have to move from one digit to the next in order without rearranging them? – Stiv Aug 31 '19 at 18:02
• It is moving without rearranging – ThomasL Aug 31 '19 at 18:06
• The solution with 13 squares sounds good - any suggestions for the bonus question? A logical solution for thie bonus question is welcome, but brute force solution is fine as well. – ThomasL Aug 31 '19 at 20:11
• good question, let's say no, so a leading zero does not count. – ThomasL Sep 1 '19 at 20:47
• yes, 0 counts as a square – ThomasL Sep 1 '19 at 21:42

For the bonus question, the best solution I have so far has

23 squares

I found precisely

8

ways of doing this (up to rotation and reflection):

A {8CF} 3 {8CF}
D 2 4 0
{8F} 6 9 1
B 7 {5E} {5E}

which contains the squares

0, 1, 4, 9, 10 (16), 19 (25), 24 (36), 40 (64), 51 (81), 64 (100), 79 (121), 90 (144), C4 (196), E1 (225), 240 (576), 349 (841), 691 (1681), 790 (1936), A29 (2601), B64 (2916), D24 (3364), D240 (53824) as well as either 510 (1296) or E10 (3600)

I don't have a proof that this is optimal, but a simulated annealing algorithm repeatedly and consistently finds one of these solutions, so I suspect these are the best, and the only ones.

• I think you are correct with your findings, well done for this bonus question! – ThomasL Sep 5 '19 at 15:31

Best solution I could come up with was,

13 squares:
1 3 7
6 2 5
9 4 8

which includes the squares,

{1, 4, 9, 16, 25, 36, 49, 64, 169, 324, 625, 729, 961}

What I tried,

Mostly trying to get as much squares with 2-digit squares (only missed 81) as possible and swapping around to make 3-digit squares and prioritizing the 169-961 double 3-digit square and other 2-3-digit doubles.
I started with 169 on a column and tried making 625 and 529 on rows, and then only 4 digits are remaining and possible to intuitively add focusing on 2-digits, or even brute-force as there are only 24 possibilities.

I just tried coding this too after seeing OP's comment, and if my program was correct,

This is the maximum and only this arrangement and rotations/reflections gives the answer.

• I coded it myself to check, you are correct that this is optimal :) – im_so_meta_even_this_acronym Aug 31 '19 at 20:58

The best I've managed so far is

12 squares

With the following

1 8 3
7 6 4
5 2 9

which has
1, 4, 9, 16, 25, 36, 49, 64, 81, 169, 529, 961

General Strategy

It's not too difficult to include all of the 2-digit squares. After that it's sensible to have 169 in there (as you get 961 for free) and then 529 is also easy to get in as we have 25.

Solution 1 with 2 as center

9 4 8
6 2 5
1 3 7

13 squares { 1,4, 9, 16, 25, 36, 49, 64, 169, 324, 625, 729, 961 }

Strategy:

I first write down the all 3 digits squares then I look for the 3 digit squares with a most solid center. means a maximum of 3 digits squares with common center number. I found there are 4 these types of squares {324, 625, 529, 729} where the common center is 2. so I made 2 is my center number and write down all the 3 digits squares. then I tried to cover the other 3 digits squares by rearranging them. then finally I look for all 2 digit squares and be able to get them mostly except 81. Also, one more thing {169 and 961} is also a good combo so don't miss it. if you see the 3 digit square list below that we can use, we can clearly see that 2 makes the most solid center so the most solid solution, after it 6 and 8 can give a better result.

Possible 3 digit squares we can use with solid centers.

1. {324, 529, 625, 729} we can either use 529 or 729 so 3 left

2. {169, 361, 961 } {we can either use 361 or 961 so 2 left}

3. {289, 784 } {we can use both}

4. {841}{196}{256}{576} {4,9,5,7 with center we will get only 1 square}
as you can see above we can use 3 of 3 digit square with 2 as center that will give us best solution. 729 is giving better solution than 529 because with 729 we are getting advantage of using one more 3 digit square 625 which is not possible with 529 because we can either use 529 or 625.

Solution 2 with 2 as center

5 7 8
3 2 4
1 6 9
same strategy 12 squares { 1,4, 9, 16, 25, 36, 49, 64, 169, 324, 529, 961 }

Solution 3 with 8 as center

2 7 1
5 8 6
3 4 9

Another 12 squares{ 1,4, 9, 16, 25, 49, 64, 81,169, 196, 289, 784 }

Solution 4 as 6 as the center.

1 5 7
8 6 2
3 4 9

12 squares same strategy { 1 ,4, 9, 16, 25, 49, 64, 81,169, 729, 961 }

• You may have noticed other answers using spoiler blocks to preserve the mystery for other would-be solvers. That's our general convention here; please conceal your answers, too :) – Rubio Sep 2 '19 at 0:19
• @Rubio sorry I am new to this site, I don't know how to do it. – Sayed Mohd Ali Sep 2 '19 at 6:44
• – Rubio Sep 2 '19 at 6:54
• @Rubio okay done thanks for the help... I am new to this site. but I am active stackoverflow user. – Sayed Mohd Ali Sep 2 '19 at 8:20