4
$\begingroup$

I know how to create a Hamiltonian path or circuit for a given grid size (in which all nodes are free). However I just wonder how to create specific type of puzzles like the ones given below. I'm looking for a comment like "First create a Hamiltonian Path or Circuit then look for the nodes or remove the ones that are bla bla...".

Puzzle #1: For a given start point, all white cells should be filled.

Puzzle #2: Create a loop passing through white cells.

What type of an algorithm should I search for? Any help would be appreciated. Thanks.

enter image description here enter image description here enter image description here

| improve this question | | | | |
$\endgroup$
5
$\begingroup$

In general, when constructing logic puzzles, you don't start with the solution. Instead, you should solve the puzzle as you construct it: place clues, deduce what you can from those clues, place more clues, and so on. This method allows you to (1) force particular deductions to be made, and (2) ensure that there is a nice human-approachable path through the puzzle.


So, to construct a logic puzzle like this, I might start with a blank grid with all cells gray. Then I'll decide on a few cells, and see where that leads me.

Here I just placed two black cells, and a few white ones around them.

enter image description here

Then I deduced as much as I possibly could from just that information:

enter image description here

Alright, I like the logic at the end of the third row there. I might decide to build off of that logic -- I'll make another cell there white, and add a turn there as well.

enter image description here

One fun bit of logic you can use in loop puzzles is parity: if you look at any region of the grid, you have to enter and exit it the same number of times. So there must be an even number of entrances/exits to any region.

Additionally, if you checkerboard-color a region with red and blue, you have to alternate red and blue squares in that region. So if there are an even number of cells in that region, and you enter on a red cell, you have to leave from a blue cell.

So here, I've built a small 'room' in the bottom right.

enter image description here

You can't leave through the other upper exit; you have to leave through the left one. So that resolves that room entirely, and lets you continue part of the loop above it too.

enter image description here

I'll also put a black block in on the left. I'll use the same trick: forcing an entry into the lower-left region, so now there are two paths in/out of it.

enter image description here

So in particular, the cell in row 4, column 3, cannot be another entrance into the lower left region: then there would be three paths in and out of it. It must go upwards instead.

(I also decided that I wanted to make the bottom middle cell white, so I didn't "force" the exit there too early.)

enter image description here

And finally, I decided to put in one more black cell to make it resolve uniquely. I chose row 5, column 3, as that one didn't give much information by itself.

enter image description here

And now the puzzle's done! All that's left is to double-check that it has a unique solution (that can be found purely logically), and you're good to go!


This is a pretty simple example, but this is how all genres of logic puzzles are constructed -- at least, by hand. (Handmade logic puzzles are generally preferred by most logic puzzlers, because they can give more room for 'forcing' clever deductions to be made.)

If you're looking to do it by computer, you can do something similar to this if you program in the deductions. But the easiest way is to just generate a loop with a few cells skipped, and then try to solve the puzzle. There's not really much else you can do beyond that.

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ This should be a general answer to any questions related to creating a puzzle! $\endgroup$ – athin Mar 22 at 0:23
  • $\begingroup$ Really helpful thank you. So what I understand is that there is no way (at least no simple way) to create such a puzzle if I already have a Hamiltonian cycle like the one in the third picture (I've added in the original post). $\endgroup$ – Joseph Mar 22 at 6:22
  • $\begingroup$ Great answer Deusovi - what software/website did you use to produce the slick images? Thanks and +1 $\endgroup$ – Stiv Mar 22 at 6:28
  • $\begingroup$ @Joseph No, there isn't, because it's not easy to "deform" a Hamiltonian cycle by adding single black cells. If you already have that solution made, it's no help for generating a puzzle, because that solution uses all cells so your puzzle would need to be blank. $\endgroup$ – Deusovi Mar 22 at 6:35
  • $\begingroup$ @Stiv I just used Google Sheets, and filled a bunch of cells with box-drawing Unicode characters! $\endgroup$ – Deusovi Mar 22 at 6:35

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.