16
$\begingroup$

This is a Haisu puzzle. Draw a path from S to G passing through all cells exactly once by connecting the centres of adjacent cells, such that when the path passes over a number N, it is on its Nth entry to the region which contains it.

Haisu

Enjoy! There is a logical path through the puzzle, so in the words of TheGreatEscaper, "No guessing, no handwavy steps, just pure logic required to solve this puzzle!"

Click on the first link or here for an example puzzle, and on the picture or here for an online solving interface.

$\endgroup$
8
+100
$\begingroup$

SOLVED!

enter image description here

Definitions:

- Path, Cell & Region: As used in the question
- Line: One of the 4 perimeter lines of any given cell
- Wall: A single black line
- Door: A wall through which the path crosses

Things to note before starting to draw:

The "12" cell in the outer region means that there must be atleast 12 doors into that region (there could be more than 12, provided they are found after the path crosses "12"). 1 door goes from S to the outer region, so atleast 11 doors come from the inner region. The number of doors out of the inner region must be the same as the number in, so there are atleast 22 doors along the border between the regions.

There are 24 cells in the inner region. The path must go into and come out of each cell exactly once, crossing two lines per cell; so 48 doors plus interior (grey) lines in total. But every time the path crosses a grey line, it simultaneously goes out of one cell and into another, meaning every grey line counts twice towards the total. So, if the path crosses $n$ grey lines, there are 48 - 2$n$ doors.

A cell with no walls requires the path to cross two grey lines to pass through it. There are 8 such cells, 4 near the corners and 4 near the centre, requiring 16 grey lines to be crossed. The 4 near the corners do not share any common lines, but three lines are shared between those near the centre. If the path were to cross one of those lines, it would count for two of the 16. Therefore, there may be up to three of the 16 counted twice, so the path must cross a minimum of 13 grey lines in order to pass through all 8 cells. This sets the upper bound on the number of doors to be 22. Hence there are exactly 22 doors and exactly 13 interior lines are crossed; three of them must be the shared lines and the remainder must all be along the perimeters of one of the 8 cells (ie not the left of "3" or the right of "7"). The path must also go from "12" to G without crossing another door.

Let's draw this in,

including the required corners:
enter image description here

Now you just have to analyse the picture (a lot):

It should be easy to see that in order to reach "1", the path must go straight across the bottom. There is then only one way into "1", and a corner above it:
enter image description here
Now look at the path leaving "12". It cannot go down, since then it is guaranteed to enter the inner region again. Then look at the corner to the bottom-right; to avoid creating a loop, the wall to the top-left must be a door. We can say a similar thing about the corner to the left of "3". We can then extend the line along the bottom:
enter image description here
Look again at the corner to the bottom-right of "12". If it were to continue upwards, the path would be unable to go from "12" to G without crossing another door. So it instead must turn left, and the path from "12" fills in the corner. To avoid trapping one of the cells adjacent to G, this corner must continue upwards, and another corner appears. The route to G is then clear, and yet another corner is filled:
enter image description here
Now look at the cell below "12". If the path were to go up, by working backwards one can see it would skip "5", "7" and "9", and if it were to continue straight, by considering the route from "1" one can see it would either reach "3" too soon or "3" would be in a loop. So it must go down; avoiding another loop gives the route out of "1", and another corner appears:
enter image description here
The way through "3" is now clear, and a number of corners can be filled and loops avoided:
enter image description here
Now look at the path from "3". It's too early to pass "7", so "7" is a corner. It is too early for this corner to continue up and join the path to "12", so it turns left, pushing the path to "12" further left also, until the path from "7" reaches "9" and the path to "12" hits the corner:
enter image description here
Now, if the path were to go down from "9", it would enter the inner region for the 9th time. To then join the path to "12", it would first have to enter the outer region for the 10th time, thus arriving at "12" on its 13th visit. So it must continue straight through "9". One more corner is revealed:
enter image description here
Now look at the path leaving "3". If it were to go down, it would have to go down again since it's too soon to reach "5". It would join up to the unjoined section near the bottom, and would subsequently be on its 5th visit to the outer region. It would then be unable to pass "5" without either a) trapping cells, or b) returning to the inner region first, thus passing "5" on its 6th visit. Hence, the path leaving "3" must continue straight, over the top of "5". It then solves itsef, by simply ensuring the path from "3" doesn't pass "5" too early or join the path from "7" until after passing "5":
enter image description here

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ You can definitely post partials! Collaboration is the key to success! $\endgroup$ – boboquack May 24 at 13:01
  • $\begingroup$ What do you make of where I'm up to so far? Are there any major pieces of logic I'm missing? Or is it just a case of now showing which paths DON't work? $\endgroup$ – jonnybolton16 May 24 at 19:54
  • 1
    $\begingroup$ @boboquack finished! $\endgroup$ – jonnybolton16 May 30 at 11:58
  • 3
    $\begingroup$ Very nice job! The checkmark goes to you for full logical writeup, and a small bounty as well. $\endgroup$ – boboquack May 31 at 5:59
  • 1
    $\begingroup$ Thanks! It was good fun $\endgroup$ – jonnybolton16 May 31 at 7:28
9
$\begingroup$

The answer is

Here x represents position where a movement is made to the outer block enter image description here

Pre Steps

You need to see the possible number of inward and outward movements you can make from the box at center. This is 22(Because you need to get in inside box 11 times and get out of it 11 times). Now observe that the perimeter of inside box is 34 units, of which 22 will be used for making in and out movements. So we have 12(34-22) units in perimeter left where we should not see any movements. But wait, there a catch. If you look at the squares circled, you can only use atmost 2 of the 3 sides(give this a thought). Since there are 10 such squares where you can only use 2 of the 3 sides, this reduces the total places where we can make in and out movements by 10 more places. So we can afford to not make in-out movement in atmost 2 (12-10) places.(Or make 1 movement in 2 of the regions circled in purple) enter image description here,

Step 1

So you can see that we already got 1 the moment we step out of S. Now we need to join it to 3 enter image description here.

Not Step 1

The below can't be a correct line diagram for step 1. The reason is simple. If you look at blue circles in the diagram, we have already missed those. And we can only afford to skip 2 of these places. So when we reach the red circle and only use 1 of its sides(instead of 2), we know that this map cannot be completed. enter image description here

Step 2

Similarly go about other numbers 5, 7, and 9 enter image description here

Step 3

Now we connect 12 to G. Now we just need to make movements in-out in the remaining squares such that the total movements when it reaches 12 is 12. enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ You got the correct answer! Unfortunately, I'm looking for some more specific logic than "you need to make in-out movement a lot" - perhaps see if you can find a more rigorous solution path. For example, why can't the step 1 look like this instead? i.stack.imgur.com/MHAbC.png $\endgroup$ – boboquack May 23 at 11:35
  • 1
    $\begingroup$ @boboquack, thanks for the feedback. Have updated it. Although there might still be some shortcomings, but I believe its clearer now $\endgroup$ – Sagar Chand May 23 at 12:14
  • 2
    $\begingroup$ You're on the right track towards a logical solution with your elaboration in pre-steps. However, in step 1, you still don't explain why the path can't do something else at the start, like i.stack.imgur.com/M5DsU.png (and many variations of something like this work for the first few numbers). It's not enough to show that one particular solution doesn't work like you've done in "Not Step 1": you need to show that all other solutions fail and that your way is correct. $\endgroup$ – boboquack May 24 at 4:33
  • 1
    $\begingroup$ @boboquack, in this particular example mentioned by you, you have already skipped 3 places (you used only 1 of the 3 sides at two places(instead of 2) in the 2nd last row and you skipped a place below '3')where there were no in-outs, whereas atmost you can afford to not make any in-outs is 2(i have explained this earlier). I do get your point though. Will try to generalize it $\endgroup$ – Sagar Chand May 24 at 5:27

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.