Author Topic: AOC++ Knight Moves  (Read 1364 times)

AOC++ Knight Moves
« on: 02 January, 2018, 11:42:06 am »
OK, based on a puzzle from the i paper the other day.

A 10x10 grid has every square visited only once by a chess knight (e.g. each move is 2 squares vertical and 1 square horizontal, or 2 squares horizontal and 1 square vertical) and the squares are marked from 1 to 100 in the order they are visited.

Here is a partial grid:-

41,92,5,58,,,3,,45,26
,,42,,,,,,,
,,99,64,,,23,56,27,
66,,,89,100,,54,,,1
39,,67,,87,60,,62,,
,69,88,95,84,71,76,,,19
,,81,,,,,,,
,9,,83,,,,,,49
37,,11,,35,78,73,16,,30
,13,,,,,,31,50,

It has a unique solution (that therefore can be deduced by logic alone, no guessing required).

My puzzle questions are:-
a) What is the most number of squares in the above partial grid (currently containing a number) that can be blanked and the grid can still be solved uniquely?
b) What is the highest total of numbers that can be removed and the grid still have a single unique solution?

[ I haven't got the answers yet but I know that removing at least a few numbers is possible. ]

Use spoilers as appropriate please...
"Yes please" said Squirrel "biscuits are our favourite things."

David Martin

  • Thats Dr Oi You thankyouverymuch
Re: AOC++ Knight Moves
« Reply #1 on: 02 January, 2018, 04:52:24 pm »
I don't follow the question. What do you mean by blanked and solving the grid?
"By creating we think. By living we learn" - Patrick Geddes

Re: AOC++ Knight Moves
« Reply #2 on: 02 January, 2018, 05:12:10 pm »
OK, here's the original grid (in a monospace font hopefully):-

(Ignore the _ at the start of the line, that's just to make it display properly.)

Code: [Select]
_ 41  92   5  58           3      45  26
_         42
_         99  64          23  56  27
_ 66          89 100      54           1
_ 39      67      87  60      62
_     69  88  95  84  71  76          19
_         81
_      9      83                      49
_ 37      11      35  78  73  16      30
_     13                      31  50

2 is missing but 1 and 3 are present. 2 can only go a knight's move from both 1 and 3, and there's only one place that can be (since the other possibility is occupied by the number 56).

The 'solved grid' will have all of the numbers filled in. For the puzzle above there is a unique solution.
"Yes please" said Squirrel "biscuits are our favourite things."

thing1

  • aka Joth
    • TandemThings
Re: AOC++ Knight Moves
« Reply #3 on: 09 January, 2018, 05:04:44 pm »
Finding the unique solution to the initial challenge is fairly straight forward (once I'd reminded myself of which end is which on a g++ compiler)

(click to show/hide)

How does AOC++ work - do you want my workings (code) too, or just the stdout?

thing1

  • aka Joth
    • TandemThings
Re: AOC++ Knight Moves
« Reply #4 on: 09 January, 2018, 05:09:43 pm »
In terms of trying to remove clues from the puzzle while still keeping a single unique solution, well....

(click to show/hide)

Re: AOC++ Knight Moves
« Reply #5 on: 09 January, 2018, 06:25:43 pm »
How does AOC++ work - do you want my workings (code) too, or just the stdout?

We work on trust but feel free to publish a link to your code if you want. I rarely bothered to look at anyone else's code during AoC itself. I was too busy mashing together my own horrific perl or C code.

Now that someone is looking at this I'll see if I get a chance tomorrow to try and find out what the actual solution to my questions are.
"Yes please" said Squirrel "biscuits are our favourite things."

thing1

  • aka Joth
    • TandemThings
Re: AOC++ Knight Moves
« Reply #6 on: 09 January, 2018, 07:19:53 pm »
This is by no means the complete solution, but the best I've got so far...
(click to show/hide)

thing1

  • aka Joth
    • TandemThings
Re: AOC++ Knight Moves
« Reply #7 on: 09 January, 2018, 07:33:50 pm »
BTW I don't understand the difference between your questions (a) and (b). They seem the same question to me.

So I'm answering "what's the fewest clue squares I can put in that puzzle and it still have one unique solution"

David Martin

  • Thats Dr Oi You thankyouverymuch
Re: AOC++ Knight Moves
« Reply #8 on: 09 January, 2018, 11:04:40 pm »
I'm really sorry - back into the melee and I don't have time to focus on this till Easter.
"By creating we think. By living we learn" - Patrick Geddes

Re: AOC++ Knight Moves
« Reply #9 on: 10 January, 2018, 08:04:22 am »
BTW I don't understand the difference between your questions (a) and (b). They seem the same question to me.

So I'm answering "what's the fewest clue squares I can put in that puzzle and it still have one unique solution"

a) is maximising count(n)
b) is maximising sum(n)

So if the maximum count of squares that could be blanked was 5 (e.g. 1, 3, 9, 11, 17) the answer to (b) might only involve blanking 2 squares (22, 23) but they have the highest sum, e.g. 1+3+9+11+17=41 but 22+23=45
"Yes please" said Squirrel "biscuits are our favourite things."

thing1

  • aka Joth
    • TandemThings
Re: AOC++ Knight Moves
« Reply #10 on: 10 January, 2018, 09:33:42 am »
Ah, got it. I've just been looking at (a). It'll be an easy tweak to attack (b).

Btw I'm playing this as practice before a coding heavy interview today, so likely to loose interest once I'm through that ordeal :)

thing1

  • aka Joth
    • TandemThings
Re: AOC++ Knight Moves
« Reply #11 on: 11 January, 2018, 10:54:22 am »
So my best results:
a) count(n) = 21
b) sum(n) = 1223

(click to show/hide)