12
$\begingroup$

enter image description here

You need to move the Coin from the S(tart) cell to the END cell.

Rules:

  1. From S you can move to cells 2,7 or 8.

  2. From BLUE cells you can only move ONE space diagonally.

  3. From YELLOW cells you can only move ONE space horizontally or vertically.

  4. From RED cells you can move in any direction BUT you must move exactly TWO spaces, both of which must be horizontal, vertical, or diagonal. (For example, from 13 you could move to S, 3, 25, 27,15.).The cell you jumped over is NOT considered as visited cell.

  5. You must visit ALL the numbered cells, and each only ONCE. You cannot go back to any cell you have already visited

  6. Of course you cannot move out of the grid—haha!

I hope this type of puzzle is not already covered. If it is, I apologize.

$\endgroup$
  • 3
    $\begingroup$ How do you consider "exactly TWO spaces"? Is a move 13 -> 21 allowed? $\endgroup$ – Ian MacDonald Mar 28 '17 at 14:02
  • 2
    $\begingroup$ NO. Verticle Horizontal or Diagonal. So from 13 you can move to Start, 15, 25, 3 and 27 only. Thanks for asking $\endgroup$ – DEEM Mar 28 '17 at 14:18
  • 3
    $\begingroup$ +1 for an interesting puzzle. But if you have a solution that doesn't require visiting S twice, why allow it? Usually with grid deduction puzzles you want to constrain solutions. Just curious what your thinking was? $\endgroup$ – GoldenGremlin Mar 28 '17 at 14:31
  • $\begingroup$ Silenus, because took me a long time to come up with my solution. So the thinking was that allowing the 2 visits to S will get to a couple of solutions fast. $\endgroup$ – DEEM Mar 28 '17 at 14:48
  • 5
    $\begingroup$ Grid deduction puzzles should have a single solution. When you open up this kind of puzzle to multiple solutions, you can no longer reach any of them through logical deduction and instead must resort to trial and error. $\endgroup$ – paramesis Mar 28 '17 at 15:02
16
$\begingroup$

This is my solution

enter image description here

Steps in numbers

S $\rightarrow$ 8 $\rightarrow$ 7 $\rightarrow$ 13 $\rightarrow$ 25 $\rightarrow$ 32 $\rightarrow$ 31 $\rightarrow$ 26 $\rightarrow$ 14 $\rightarrow$ 19 $\rightarrow$ 20 $\rightarrow$ 27 $\rightarrow$ 33 $\rightarrow$ 35 $\rightarrow$ 34 $\rightarrow$ 29 $\rightarrow$ 28 $\rightarrow$ 21 $\rightarrow$ 16 $\rightarrow$ 2 $\rightarrow$ 9 $\rightarrow$ 15 $\rightarrow$ 10 $\rightarrow$ 3 $\rightarrow$ 4 $\rightarrow$ 18 $\rightarrow$ 11 $\rightarrow$ 5 $\rightarrow$ 6 $\rightarrow$ 12 $\rightarrow$ 17 $\rightarrow$ 22 $\rightarrow$ 23 $\rightarrow$ 30 $\rightarrow$ 24 $\rightarrow$ END

$\endgroup$
  • 1
    $\begingroup$ Kudos. Was there a method you used Techidiot? $\endgroup$ – DEEM Mar 28 '17 at 16:09
  • $\begingroup$ Ahh nice work.. I kept missing that 16 -> 2 step and it was where I kept getting stuck $\endgroup$ – n_plum Mar 28 '17 at 16:24
  • 1
    $\begingroup$ @DeepakMahulikar You can accept this answer, 12 mins have passed :) $\endgroup$ – EKons Mar 28 '17 at 16:25
10
$\begingroup$

1 -> 8 -> 7 -> 13 -> 15 -> 22 -> 23 -> 30 -> 29 -> 28 -> 21 -> 14 -> 19 -> 20 -> 25 -> 32 -> 31 -> 26 -> 16 -> 2 -> 9 -> 3 -> 4 -> 18 -> 11 -> 10 -> 5 -> 6 -> 12 -> 17 -> 24 -> 34 -> 27 -> 33 -> 35 -> 36

Ah, I see someone else got there first. Interesting that we got different solutions - so there's at least 2!

One thing that was useful was a bit of accounting. Imagine overlaying the grid onto a black and white checkerboard, with the start and end white.

Then there are 7 blues on black, 7 blues on white, 4 reds on black, 2 reds on white, 7 yellows on black and 7 yellows on white.

Now note that blues and reds always move to the same color and yellows always change color, and that we need to leave each of these squares exactly once. Therefore the total number of black squares we will move on to is 18 (7+4+7) and the total number of white squares we will move on to is 16 (7+2+7).

Now we know that we need to move onto a total of 17 white squares and 18 black squares, and the only square we haven't counted is the starting square. So we need to start by moving on to a white square, which means that 1 -> 8 is the only possible first move.

$\endgroup$
  • 1
    $\begingroup$ Very smart, the last comment. $\endgroup$ – DEEM Mar 28 '17 at 20:53
4
$\begingroup$

I opted to brute force it. There appear to be 9628 solutions. Code and solutions over here.


The puzzle itself presents a directed graph and then asks you to find a path that hits all nodes once and only once, starting and ending at specific nodes. This is essentially the Traveling Salesman Problem. In the general case this is known to be a NP-hard problem (i.e.: there isn't much in the way of shortcuts). I imagine a similar puzzle designed around the arrangement and discovery of "artifacts" (like 1->8 and 31->26) would make for a puzzle where brute forcing is less desirable.

I'm best with C#, JavaScript, and Python these days. Out of those Python seemed the obvious choice for quick a mock-up of this sort.

The algorithm started out as a straight-up recursive brute force using just a tracking queue. Optimizations included:

  • adding a set (they're much faster for searching collections),
  • a fixed length queue with separate actual length tracking (faster to change values rather than .append()/del; since searching the set is much faster, we can get away with using .add()/.discard(); this also allowed me to remove the list copying I had going on),
  • move stuff out of the inner loop

Doing all of this feels like code golf but you're optimizing for speed rather than size. There's probably more optimizations that could be made but, by then, it was fast enough that I'd gotten an answer before I'd figured out the next optimization. Even so, it still took 15-20 minutes to run and about an hour to code.

cells = [
    None,
    [2,7,8],                  #  1 start
    [7,9],                    #  2 b diagnal
    [2,4,9],                  #  3 y adjacent
    [2,6,14,16,18],           #  4 r 2space
    [4,6,11],                 #  5 y
    [5,12],                   #  6 y
    [8,13],                   #  7 y
    [2,7,9,14],               #  8 y
    [3,8,10,15],              #  9 y
    [3,5,15,17],              # 10 b
    [5,10,12,17],             # 11 y
    [5,17],                   # 12 b
    [3,15,25,27],             # 13 r
    [7,9,19,21],              # 14 b
    [8,10,20,22],             # 15 b
    [2,4,6,14,18,26,28,30],   # 16 r
    [10,12,22,24],            # 17 b
    [11,23],                  # 18 b
    [13,20,25],               # 19 y
    [13,15,25,27],            # 20 b
    [14,16,26,28],            # 21 b
    [16,21,23,28],            # 22 y
    [16,18,28,30],            # 23 b
    [10,12,22,34,36],         # 24 r
    [20,32],                  # 25 b
    [14,16,28],               # 26 r
    [21,26,28,33],            # 27 y
    [21,23,33,35],            # 28 b
    [23,28,30,35],            # 29 y
    [24,29,36],               # 30 y
    [26],                     # 31 b
    [26,31,33],               # 32 y
    [19,21,23,31,35],         # 33 r
    [27,29],                  # 34 b
    [29,34,36]                # 35 y
]

results = []
historyl = [None] * len(cells)
historys = set()
f = open('out.txt','w')

def find(this = 1, depth = 0):
    #print historyl, this
    if this == 36 and depth == 35:
        r = historyl[:depth]
        r.append(this)
        results.append(r)
        print r
        print >>f, r
    elif this != 36:
        historyl[depth] = this
        for x in cells[this]:
            if x not in historys:
                historys.add(this)
                find(x, depth+1)
                historys.discard(this)

find()
f.close()
$\endgroup$
  • 1
    $\begingroup$ Please can you edit some of your work into this answer to flesh it out? Link-only answers are discouraged here, since if the link goes dead the answer becomes essentially useless. $\endgroup$ – Rand al'Thor Mar 28 '17 at 23:49
  • 1
    $\begingroup$ @DrXorile Project Euler questions always have a way to optimize so they run under a minute. I don't think that's actually possible with this particular puzzle arrangement. It'd need more situations like the 1->8 logic. (There's another obvious one at 31->26 but I think that's it.) As it stands, this takes 15-20 minutes to run on today's average laptop. $\endgroup$ – Ouroborus Mar 29 '17 at 4:51
  • 1
    $\begingroup$ I confirm 9628 solutions. Thanks to Dr. Xorile for the excellent point about starting at 8. That reduced the running time substantially. $\endgroup$ – saulspatz Mar 29 '17 at 5:31
  • 1
    $\begingroup$ Nice recursion too. For non-coders, to understand recursion, you first need to understand recursion... $\endgroup$ – Dr Xorile Mar 29 '17 at 16:08
  • 1
    $\begingroup$ For the coders out there: Can you code this type of puzzle to obtain one single solution? May be a grid which only allows either 2 diagonal or 2 horizontal or vertical moves only? That would be interesting $\endgroup$ – DEEM Mar 29 '17 at 16:59
3
$\begingroup$

Partial answer:

Start with corners obviously, these are most restricted. Bottom left corner works: 25->32->33->31->26, you cannot reach 32 and continue any other way.

EDIT: Given one solution (maybe not the only one), I found out I forgot about 24->34 possibility. The upper corner thingy works, rest is maybe a possibility but not a certainty.

Then

23->30->29->35->34->27 is the only way to reach 34 with the former 5 numbers blocked.

Plus

5->6->12->17->24->END is now the only remaining way to reach number 6 and end.

I will continue later to see how far I can go without any guessing or assumptions.

$\endgroup$
0
$\begingroup$

The answer is

S,2,7,8,9,3,4,6,5,11,12,17,10,15,22,16,18,23,30,24,34,27,21,14,19,20,13,25,32,31,26,28,33,35,29,E

Image:-

enter image description here red (2 spaces) have dotted lines

$\endgroup$
  • $\begingroup$ Whoops. Edited. $\endgroup$ – Karan Atree Mar 28 '17 at 15:43
  • 5
    $\begingroup$ but now you have yellow (29) moving diagonally $\endgroup$ – paramesis Mar 28 '17 at 15:45
  • $\begingroup$ Note that 1->8 can be shown to be the first move (see my solution for proof). $\endgroup$ – Dr Xorile Mar 28 '17 at 16:46
  • $\begingroup$ There is still one solution out there $\endgroup$ – DEEM Mar 28 '17 at 23:19

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.