7
$\begingroup$

Inspired by this puzzle : Integers around a circle with consecutive pairs adding to a square

The integers 1 to 50 are placed around a circle in such a way that the difference of any two of them which are adjacent is a perfect square. Of these integers, some numbers are then removed. Restore them

enter image description here

$\endgroup$
7
$\begingroup$

Here we go: I think this is right..

1 - 50 - 14 - 39 - 3 - 28 - 44 - 8 - 33 - 49 - 13 - 38 - 2 - 27 - 43 - 7 - 32 - 23 - 48 - 12 - 37 - 21 - 46 - 30 - 5 - 41 - 16 - 25 - 34 - 18 - 9 - 45 - 29 - 4 - 20 - 36 - 11 - 47 - 22 - 31 - 40 - 24 - 15 - 6 - 42 - 17 - 26 - 35 - 19 - 10

Disclaimer: this was programatically solved - I got part way in solving it but like others had problems finishing it off.

The method of solving was to create a candidate list of values for each cell and then prune them down. The pruning down was done in two ways. The first is to compare each candidate with every possible value in its neighbouring cells. If the candidate is not a square difference of at least one value in each side then it is no longer a candidate. This allows you to prune down many things.

The other check needed was to see if any of the unset values only appear in the candidate list of a single cell. If so then obviously that value can be set as confirmed for that cell.

Following is the step by step guide from my program as it was pruning down possibilities. It starts with every unfixed cell being able to take all possible values and does the easy pruning in the first pass. This was easier than initializing each empty cell more intelligently.

Of note is that when it says Removing items from position N: x,y,z that means that those values are not possible by examining neighbouring cells. It doesn't explicitly list removing candidates due to fixing a number. That is assumed.

Removing items from position 1: 3,6,7,8,12,13,14,16,18,20,22,23,24,27,28,29,30,33,34,35,36,38,40,41,42,43,45,46,47
Removing items from position 2: 3,6,7,8,10,12,13,16,18,20,22,23,24,26,27,28,29,33,34,36,37,40,41,42,43,45,46,47,50
Removing items from position 4: 6,7,8,10,12,13,16,18,20,22,24,26,27,28,29,33,34,36,37,41,42,45,46,47,50
Removing items from position 5: 3,6,7,8,10,12,13,14,16,18,20,22,23,24,26,27,29,30,33,34,35,36,37,38,40,41,42,43,45,46,47,50
Fixed value for position 5 to 28 (only value that can make a square with both of its neighbours)
Removing items from position 7: 3,6,7,10,12,13,14,16,18,20,22,23,24,26,27,29,30,33,34,36,37,38,41,42,46,47,50
Removing items from position 8: 3,6,7,8,10,12,13,14,16,18,20,22,23,26,27,28,29,30,34,35,36,37,38,40,41,42,43,45,46,47,50
Removing items from position 10: 3,6,7,8,10,12,14,16,18,20,22,23,26,27,28,29,30,34,35,36,37,38,41,42,43,46,47
Removing items from position 11: 3,6,7,8,10,12,13,14,16,18,20,22,23,24,26,27,28,29,30,33,34,35,36,37,40,41,42,43,45,46,47,50
Fixed value for position 11 to 38 (only value that can make a square with both of its neighbours)
Removing items from position 13: 7,8,10,12,13,14,16,20,22,23,24,26,28,29,30,33,34,35,36,37,40,41,42,43,45,46,47,50
Removing items from position 14: 3,6,8,16,20,24,30,33,35,38,40,41,45,46,50
Removing items from position 15: 3,6,8,10,12,13,14,18,20,22,24,26,27,29,30,34,35,37,38,40,42,43,45,46,47,50
Removing items from position 17: 3,6,7,8,10,12,13,14,16,18,20,22,24,26,27,28,29,30,33,34,35,36,37,38,40,41,42,43,45,46,47,50
Fixed value for position 17 to 23 (only value that can make a square with both of its neighbours)
Removing items from position 19: 3,6,7,8,10,13,14,16,18,20,22,24,26,27,28,29,30,33,34,35,36,37,38,40,41,42,43,45,46,50
Removing items from position 20: 3,6,7,8,10,12,13,14,16,18,20,23,24,26,27,28,29,30,33,34,35,36,38,40,41,42,43,45,47,50
Removing items from position 22: 3,6,7,8,10,13,14,16,18,23,24,26,27,28,29,33,34,35,36,38,40,41,42,43,45,47,50
Removing items from position 23: 3,7,8,10,12,13,16,18,20,22,23,24,26,27,28,29,33,34,35,36,37,38,40,42,43,45,46,47,50
Removing items from position 25: 3,7,8,10,12,13,16,18,20,22,23,24,26,27,28,29,33,34,35,36,37,38,40,42,43,45,46,47,50
Removing items from position 26: 3,6,7,8,10,12,13,14,18,20,22,23,24,27,28,30,33,35,36,37,38,40,41,42,43,45,46,47
Removing items from position 28: 3,6,7,8,10,12,13,14,18,20,22,23,27,28,30,33,35,36,37,38,40,42,43,45,46,47
Removing items from position 29: 3,6,7,12,14,16,20,22,23,24,26,27,28,29,30,33,35,36,37,38,40,41,42,43,46,47,50
Removing items from position 31: 3,6,7,12,14,16,20,22,23,24,26,27,28,29,30,33,35,36,37,38,40,41,42,43,46,47,50
Removing items from position 32: 3,6,7,8,10,12,13,14,16,18,22,23,24,26,27,28,30,33,34,35,36,37,38,40,41,42,43,45,46,47,50
Removing items from position 34: 6,7,10,12,14,16,18,22,23,24,26,27,28,30,33,34,35,36,37,38,41,42,43,45,46,47,50
Removing items from position 35: 3,6,8,10,13,14,16,18,22,23,24,26,27,28,29,30,33,34,35,37,38,40,41,42,43,45,46,47,50
Removing items from position 37: 3,6,8,13,14,16,18,22,23,24,26,28,29,30,33,34,35,37,38,40,41,42,43,45,46,50
Removing items from position 38: 3,7,8,10,12,13,14,16,18,20,23,24,26,28,29,30,33,34,36,37,38,41,42,43,45,46,47,50
Removing items from position 40: 3,7,8,10,12,13,14,16,18,20,23,24,26,28,29,33,34,36,37,38,41,42,43,45,46,50
Removing items from position 41: 3,7,8,10,12,13,16,18,20,22,23,26,27,28,29,30,33,34,35,36,37,38,40,41,42,43,45,46,47,50
Removing items from position 43: 3,7,8,10,12,13,18,20,22,23,26,27,28,29,30,33,34,35,36,37,38,41,42,43,45,46,47,50
Removing items from position 44: 3,6,7,10,12,14,16,20,22,23,24,26,27,28,29,30,34,35,36,37,38,40,41,43,45,46,47,50
Removing items from position 46: 3,6,7,10,12,14,20,22,23,24,27,28,29,30,34,35,36,37,38,40,41,43,45,46,47,50
Removing items from position 47: 3,6,7,8,12,13,14,16,18,22,23,24,26,27,28,29,30,33,34,36,37,38,40,41,42,43,45,46,47,50
Removing items from position 49: 3,6,7,8,12,13,14,16,18,20,22,23,24,26,27,28,29,30,33,34,35,36,37,38,40,41,42,43,45,46,47,50
Fixed value for position 49 to 10 (only value that can make a square with both of its neighbours)
Loop iteration finished. 21 values now fixed. 29 left to find.

Removing items from position 1: 37
Removing items from position 4: 14,30,35,40,43
Fixed value for position 4 to 3 (only value that can make a square with both of its neighbours)
Removing items from position 7: 35,43,45
Removing items from position 10: 24,33,40,45,50
Fixed value for position 10 to 13 (only value that can make a square with both of its neighbours)
Removing items from position 14: 13,14,18,22,26,29,36,37,47
Removing items from position 22: 12,20
Removing items from position 25: 6
Removing items from position 28: 16,26
Removing items from position 31: 8,18,34
Removing items from position 37: 12,20,27
Removing items from position 40: 6,27,35,47
Removing items from position 43: 16,40
Removing items from position 46: 8,13,18,33,42
Fixed value for position 14 to 43 (only cell with value left as a possibility)
Loop iteration finished. 24 values now fixed. 26 left to find.

Removing items from position 13: 6
Removing items from position 15: 16,33,36,41
Fixed value for position 15 to 7 (only value that can make a square with both of its neighbours)
Fixed value for position 44 to 42 (only cell with value left as a possibility)
Loop iteration finished. 26 values now fixed. 24 left to find.

Removing items from position 38: 6
Removing items from position 43: 14,24
Fixed value for position 43 to 6 (only value that can make a square with both of its neighbours)
Fixed value for position 8 to 33 (only cell with value left as a possibility)
Loop iteration finished. 28 values now fixed. 22 left to find.

Removing items from position 7: 40
Fixed value for position 7 to 8 (only value that can make a square with both of its neighbours)
Removing items from position 22: 22
Removing items from position 40: 22
Loop iteration finished. 29 values now fixed. 21 left to find.

Removing items from position 28: 24
Removing items from position 35: 12
Fixed value for position 19 to 12 (only cell with value left as a possibility)
Fixed value for position 41 to 24 (only cell with value left as a possibility)
Fixed value for position 37 to 47 (only cell with value left as a possibility)
Loop iteration finished. 32 values now fixed. 18 left to find.

Removing items from position 20: 22,46
Fixed value for position 20 to 37 (only value that can make a square with both of its neighbours)
Removing items from position 38: 27,35,40
Fixed value for position 38 to 22 (only value that can make a square with both of its neighbours)
Removing items from position 40: 30
Fixed value for position 40 to 40 (only value that can make a square with both of its neighbours)
Fixed value for position 13 to 27 (only cell with value left as a possibility)
Fixed value for position 35 to 36 (only cell with value left as a possibility)
Fixed value for position 22 to 46 (only cell with value left as a possibility)
Loop iteration finished. 38 values now fixed. 12 left to find.

Removing items from position 23: 14,41
Fixed value for position 23 to 30 (only value that can make a square with both of its neighbours)
Removing items from position 34: 29
Fixed value for position 34 to 20 (only value that can make a square with both of its neighbours)
Fixed value for position 29 to 18 (only cell with value left as a possibility)
Fixed value for position 31 to 45 (only cell with value left as a possibility)
Loop iteration finished. 42 values now fixed. 8 left to find.

Removing items from position 26: 26,29,34
Removing items from position 28: 29,41,50
Fixed value for position 28 to 34 (only value that can make a square with both of its neighbours)
Removing items from position 46: 16
Fixed value for position 46 to 26 (only value that can make a square with both of its neighbours)
Fixed value for position 26 to 16 (only cell with value left as a possibility)
Fixed value for position 32 to 29 (only cell with value left as a possibility)
Fixed value for position 25 to 41 (only cell with value left as a possibility)
Fixed value for position 1 to 50 (only cell with value left as a possibility)
Loop iteration finished. 48 values now fixed. 2 left to find.

Removing items from position 2: 35
Fixed value for position 2 to 14 (only value that can make a square with both of its neighbours)
Fixed value for position 47 to 35 (only cell with value left as a possibility)
Loop iteration finished. 50 values now fixed. 0 left to find.

$\endgroup$
  • $\begingroup$ I was on the right track. But what do you do in places where there are three missing numbers? $\endgroup$ – Mhmd Jan 19 '18 at 15:32
  • $\begingroup$ @Mhmd: You can continue to use the same elimination logic. Interestingly looking up where my program fixed the middle of that group of three it actually fixed it before the two either side by it being the only cell that could possibly have that value (ie the value it has had been eliminated from every other cell). $\endgroup$ – Chris Jan 19 '18 at 15:40
  • 1
    $\begingroup$ @Mhmd: I've added in the solution logic from my program if you want to follow along. Its quite verbose though so maybe not the easiest thing to follow... $\endgroup$ – Chris Jan 19 '18 at 15:52
  • $\begingroup$ @Saeïdryl : Thanks for the graphical representation of the answer. :) $\endgroup$ – Chris Jan 19 '18 at 16:09
5
$\begingroup$

Nothing in this puzzle mentioned not using coding, but I didn't write a fully-fledged program to solve it. Instead, I just used it as a "tool" to speed up a few calculations. Still did it mostly by hand:

enter image description here

How I did it:

I wrote the numbers as an array and iterated through each missing spot and put them in a "missing numbers" array. Then, I'd check its neighbors and calculate which numbers from the missing ones would give a square number difference. Sometimes there would be multiple before I could calculate the next one, but I still calculated every possible instance. When it repeated or gave no result, I'd remove it from the possibilities for that spot. Rinse and repeat throughout the chain until I had a full list of candidates. Then I looked through which numbers I could be sure of (if it was the only one in that spot, or if it showed up in that spot's possibilities only and nowhere else). Then I'd remove the solved numbers from other spots, as well as removing the numbers that preceded them if it was a single one. And by this process of elimination, knowing each number from 1 through 50 showed once, I could narrow it down to this single possible list. Then I double-checked just to make sure it was right :P

It was great fun solving it mostly by hand rather than writing complex code to solve it for me!

EDIT: Only now saw there was another correct answer before mine. Oh well, better luck next time

$\endgroup$
  • $\begingroup$ Yeah, I mean I got there before you but definitely +1 for that diagram - saves having to do all that mental arithmetic to confirm yourself. :) $\endgroup$ – Chris Jan 19 '18 at 16:16
2
$\begingroup$

My attempt - with 5 missing

Starting at $1$, we have

$$\small1-26-30-39-3-28-44-8-24-49-45-?-2-38-34-33-32-23-48-47-46-21-37-41-5-14-50-25-29-13-9-18-?-4-20-36-11-?-22-31-35-?-15-6-42-17-16-?-19-10-1$$

The missing numbers are $7, 12, 27, 40, 43$. Note that $43-7=6^2$.

$\endgroup$
  • $\begingroup$ I had a few missing numbers too, but too frustrated to try it a 3rd time :/ $\endgroup$ – Saeïdryl Jan 19 '18 at 10:10

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.