Yet Another Cycling Forum

General Category => The Knowledge => Ctrl-Alt-Del => Topic started by: Greenbank on 02 January, 2018, 11:42:06 am

Title: AOC++ Knight Moves
Post by: Greenbank 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...

Title: Re: AOC++ Knight Moves
Post by: David Martin on 02 January, 2018, 04:52:24 pm

I don't follow the question. What do you mean by blanked and solving the grid?

Title: Re: AOC++ Knight Moves
Post by: Greenbank 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.

Title: Re: AOC++ Knight Moves
Post by: thing1 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)

Code: [Select]

*** START POINT:
 41 92  5 58  .  .  3  . 45 26
  .  . 42  .  .  .  .  .  .  .
  .  . 99 64  .  . 23 56 27  .
 66  .  . 89100  . 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  .
***
Found 1 solutions!
 41 92  5 58 43 24  3 22 45 26
  6 65 42 91  4 57 44 25  2 21
 93 40 99 64 59 90 23 56 27 46
 66  7 94 89100 63 54 47 20  1
 39 98 67 70 87 60 85 62 55 28
  8 69 88 95 84 71 76 53 48 19
 97 38 81 68 77 86 61 72 29 52
 12  9 96 83 80 75 32 51 18 49
 37 82 11 14 35 78 73 16 33 30
 10 13 36 79 74 15 34 31 50 17



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

Title: Re: AOC++ Knight Moves
Post by: thing1 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)

At least the first seven steps (that is,  Knight moves 3, 5, 9, 11, 13, 16 and 19) can be removed while the puzzle still has a single unique solution. Trouble is my current solution finder is much worse than exponential search time for the number of contiguous unknown moves, so I need to rethink my approach to find exactly how many can be removed.  If all else fails, I'll have to dig out the idiot's guide to MapReduce.

Title: Re: AOC++ Knight Moves
Post by: Greenbank on 09 January, 2018, 06:25:43 pm

Quote from: thing1 on 09 January, 2018, 05:04:44 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.

Title: Re: AOC++ Knight Moves
Post by: thing1 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)

So far, I can blank 16 squares, so down to 28 'clues' (down from 44 in the OP) and it still only has one unique solution.

Code: [Select]

Found a puzzle with 28 clues that still has exactly one solution!..
  . 92  5 58  .  .  .  . 45 26
  .  . 42  .  .  .  .  .  .  .
  .  . 99  .  .  . 23  .  .  .
 66  .  . 89  .  . 54  .  .  1
 39  .  .  . 87  .  . 62  .  .
  . 69  . 95 84  . 76  .  . 19
  .  . 81  .  .  .  .  .  .  .
  .  9  .  .  .  .  .  .  . 49
  .  .  .  . 35  . 73 16  . 30
  . 13  .  .  .  .  .  .  .  .
==

Update1: got it down to two slightly different puzzles each with 26 filled squares that have a single solution.

Code: [Select]

Found a puzzle with 26 clues that still has exactly one solution!..
  . 92  5 58  .  .  .  . 45  .
  .  .  .  .  .  .  .  .  .  .
  .  . 99  .  .  . 23  . 27  .
 66  .  . 89100  . 54  .  .  1
 39  .  .  . 87  .  . 62  .  .
  . 69  . 95  .  .  .  .  . 19
  .  . 81  .  .  .  .  .  .  .
  .  9  .  .  .  .  .  .  . 49
  .  .  .  . 35 78 73  .  .  .
  . 13  .  .  .  .  . 31  .  .

AND

Found a puzzle with 26 clues that still has exactly one solution!..
  . 92  5 58  .  .  .  . 45 26
  .  .  .  .  .  .  .  .  .  .
  .  . 99  .  .  . 23  .  .  .
 66  .  . 89  .  . 54  .  .  1
 39  .  .  . 87  .  . 62  .  .
  . 69  . 95  .  . 76  .  . 19
  .  . 81  .  .  .  .  .  .  .
  .  9  .  .  .  .  .  .  . 49
  .  .  .  . 35  . 73 16  . 30
  . 13  .  .  .  .  .  .  .  .


Update2: Down to 25 clues (so 19 blanked vs OP)

Code: [Select]

Found a puzzle with 25 clues that still has exactly one solution!..
  . 92  5 58  .  .  .  . 45 26
  .  .  .  .  .  .  .  .  .  .
  .  . 99  .  .  . 23  .  .  .
 66  .  . 89  .  . 54  .  .  1
 39  .  .  . 87  .  . 62  .  .
  . 69  . 95  .  . 76  .  . 19
  .  . 81  .  .  .  .  .  .  .
  .  9  .  .  .  .  .  .  . 49
  .  .  .  . 35  . 73  .  . 30
  . 13  .  .  .  .  .  .  .  .


[/spolier]

Title: Re: AOC++ Knight Moves
Post by: thing1 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"

Title: Re: AOC++ Knight Moves
Post by: David Martin 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.

Title: Re: AOC++ Knight Moves
Post by: Greenbank on 10 January, 2018, 08:04:22 am

Quote from: thing1 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"

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

Title: Re: AOC++ Knight Moves
Post by: thing1 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 :)

Title: Re: AOC++ Knight Moves
Post by: thing1 on 11 January, 2018, 10:54:22 am

So my best results:
a) count(n) = 21
b) sum(n) = 1223

(click to show/hide)

Code: [Select]


(a)
Found a puzzle with 23 clues that still has exactly one solution!..
  . 92  . 58  .  .  .  . 45  .
  .  .  .  .  .  .  .  .  .  .
  .  . 99  .  .  . 23  .  .  .
 66  .  . 89  .  . 54  .  .  1
 39  .  .  . 87  .  . 62  .  .
  . 69  . 95  .  . 76  .  . 19
  .  . 81  .  .  .  .  .  .  .
  .  9  .  .  .  .  .  .  . 49
  .  .  .  . 35  . 73  .  . 30
  . 13  .  .  .  .  .  .  .  .


(b)
Found a puzzle with 26 clues that still has exactly one solution! sum = 1223
  . 92  5 58  .  .  3  .  . 26
  .  .  .  .  .  .  .  .  .  .
  .  . 99  .  .  . 23  . 27  .
  .  .  .  .  .  . 54  .  .  1
 39  . 67  .  .  .  . 62  .  .
  .  . 88  . 84 71  .  .  . 19
  .  . 81  .  .  .  .  .  .  .
  .  9  .  .  .  .  .  .  .  .
 37  . 11  . 35  .  . 16  . 30
  . 13  .  .  .  .  . 31  .  .