How does one go about creating a new grid-deduction puzzle?

Question

The grid-deduction tag covers puzzles like Sudoku, Kakuro, etc. where the goal is to fill in a grid of numbers [/letters/colours] in a unique way by logical deduction from some predetermined rules and information. These can be a joy to solve, and I've often wondered how people create them. It's not as easy as it may look, because you want to hit the sweet spot between redundancy (including too much information) and unsolvability (including too little information).

Some of these puzzles can take a really long time and many clever deductions to solve correctly. Surely the puzzle creator doesn't try different configurations and actually work through a solution for each one until they find a sufficiently hard but still uniquely solvable puzzle.

I suppose an easy (for some people) method would be to program a computer to be able to solve that type of puzzle and then plug each iteration in until you find one that's hard yet solvable. But that would be considerably harder for new puzzles like Ripple Effect than well-established ones like Sudoku.

How does one go about creating a new grid-deduction puzzle?

Answer 1

When constructing a puzzle like this, the important thing to remember is that you should solve the puzzle as you construct it. The general process of construction goes like this:

• Place clues to make a specific deduction.
• Deduce everything you possibly can from those clues; write those deductions in.
• Place more clues that work with your previous information to allow a new deduction.
• Repeat steps 2-3 until you have completed the puzzle.
• Solve the puzzle from scratch to ensure it is unique.

So, the process involves alternating solving and construction. This allows you to force specific deductions to be made -- making your puzzles much more interesting for the solver.

---

As a demonstration, I'll construct a Tapa puzzle here. I've never constructed a Tapa before, so this should demonstrate how these principles are widely applicable. (The final puzzle was shared as a separate question here.)

Tapa is a genre with the rules:

• Shade some cells to form a "wall" - a connected group of cells with no 2×2 square fully shaded.
• Some cells have one or more numbers in them. These cells cannot be shaded. The numbers give the connected runs of shaded cells in the eight cells around them. (This is like a Picross/Nonogram puzzle, but "bent into a circle" rather than giving a row or column.)

Here's an example Tapa, with its solution:

For instance, around the central clue, there are two single black cells on the left two corners, and a "run" of three black cells on the right side. Similarly, around the bottom left clue there is a run of 3 (in the cells below, below-right, and right of the clue) and a run of 1 (the cell above the clue). In the top right, there is only a run of 5 (all five cells around the clue).

For the actual puzzle, I'll be using the puzz.link editor -- it's a helpful site for constructing a lot of different genres.

---

So, to start I'll need a break-in for the puzzle. Here, I decide to place a (3,3) clue near a corner. (And I've decided I want rotational symmetry of my clue placement, so I'll put a question mark in the opposite position.)

A [3,3] clue gives a lot of information -- it tells you that only two of the eight cells are unshaded, and they're diametrically opposite each other.

From this I can deduce that these two cells must be shaded: if not, they would trap some shaded cells in the upper right.

Now that I've forced that deduction, I'll place another clue building off of that. Here, I place a (3) next to one of the known-to-be-shaded cells: this means that none of the cells under, left of, or below-left of the (3) clue can be shaded, because they'd be too far from the one we already know to be shaded.

And that means that the (3) must be satisfied by its entire top row, because anything else would either break connectivity or put an extra shaded square by the (3).

Next, I want to use those shaded cells that are sticking out, but I should also probably resolve that cramped lower right area.

I'll drop something in the lower right corner and something in the second row, and their symmetric counterparts too. This should let me make progress in both the top left and lower right corners. I might fiddle around with these placements and clues for a bit to see what gives the most interesting logic.

After a bit of experimentation, I come up with this. Maybe this will work? I'm not entirely sure, though... at the moment it looks like the lower right is more constrained than the upper left, and I can't resolve the upper left without more clues.

So I'm not sure this will work. I back up and give it another shot.

Yeah, I like this better. I still haven't decided on those central clues, but I think there's a number of ways I could pull those off (and I can move them if I want, too). But the (2,4) rules out the square to its lower left, and that lets me resolve the top area of the grid.

Meanwhile, in the lower right, the (2,1) lets me resolve that relatively empty area between it and the 3 with connectivity logic. (I can't fill both of the squares I've marked with an X in between, because that would mean the bottom right corner is trapped.)

After some more experimentation, I notice that those two clues I wasn't sure about would give too much information, so I remove them.

I like this so far, but I'm slightly worried about the wide-open center. Hopefully I can choose clues for the other question marks to make sure it's not a problem? Maybe I'll have to add a clue in row 4, column 2, though. That's one of the few places I can add one.

I realize that adding one there, in its counterpart I can specify a (2) or (3). A (2) would shortcut some of the logic from the very start of the puzzle, because the top right corner couldn't escape downwards without breaking the (2) too. But a (3) would leave an ambiguity with the (2,1) clue that I would need to resolve... I'll go with the (3) for now, and see if I can resolve that ambiguity some other way.

(I also notice I could preserve a fair bit of logic by making the top (1) clue into a (1,1). I'll keep that in mind for further experimentation.)

After a few more tries, I'll place a (3) in that slot. What about the left side? A (5) for the top clue wouldn't give away too much information by itself, but it could pair with another clue for interesting results: how about three 1s?

No, that would be doable at the start of the puzzle. I want something that uses the cell I already have shaded. Maybe a (1,3) and a (3,2) instead? I'll try that out and see how it works.

Hm, I can resolve the lower right with connectivity, but there's a bigger concern: the center looks like it won't be unique. I'll back up a bit and place clues in R4C3 and its counterpart. A (1,2) on the right will force that connectivity deduction, and a (2,3) on the left should work to not give too much information away.

Now we have three separate strands that must be connected. I'll place a 5 in the lower left clue position and two 6s nearby -- now all the remaining squares are an alternating "chain", where if one is shaded then the other is not (either from the 2x2 rule or from a nearby clue).

And finally, I try turning the top left clue into a (1,1) as I mentioned earlier. This would let me resolve the chain uniquely, but it would bypass a lot of logic... instead I'll leave it as a (1), and instead turn the lower (6) into a (7). And we're done!

Now all that's left is to testsolve the puzzle to make sure I haven't made any mistakes along the way, and I'm good to go!

---

You might notice that this reads a lot like my explanations of how I solve logic puzzles. This is no accident! Constructing and solving are very similar -- as I mentioned earlier, when you construct a puzzle, you should be solving the puzzle along with your construction.

A lot of my thoughts that I wrote out were partially based on intuition about how Tapa works, so they might have been slightly harder to follow even if you understood the deductions. While I've never written a Tapa before today, I have solved a fair amount of them -- experience with genres helps.

And finally, some other tips that didn't fit cleanly into this:

• When placing clues, it helps to think about your previous deductions that you want to force. Sometimes a clue will accidentally make a previous deduction trivial: for more interesting puzzles, that's usually something you want to avoid.
• In genres with "global" constraints, such as Double Choco and Statue Park, you should generally decide on those global constraints first: in Double Choco, draw your grid shading first, and in Statue Park, decide on your bank first. Then, for the rest of the puzzle, you can place clues that can be freely modified: in these cases, the number clues and the dots.
• Sometimes, a genre has only "global" constraints, like Star Battle or Spiral Galaxies. These are much harder to construct - often, you may have to take separate notes saying things like "the upper left area should be divided into 3 regions" or "there should be no more galaxy centers in the right three columns of rows 1-4". By slowly narrowing down these global constraints, you can figure out deductions as you go in a similar way to other genres. But it will still be much harder to do so, and a lot more rewinding may be necessary.
• If you're trying to force a specific solution (say, for puzzle hunt extraction), it will also likely be more difficult. The process will be similar, but this time, instead of just backtracking when you hit a contradiction/ambiguity, you will also need to backtrack when a deduction doesn't lead to the desired solution.
• In cases where you need to force something for outside reasons, it's often better to only require a solution with certain characteristics, and have the rest of it be 'free'. For one reason or another, many solutions aren't forceable at all in a specific genre, or any way to force them will make the logical path uninteresting. This is why many puzzle hunts just use extra grids of letters for extraction from logic puzzles, rather than building something else into the puzzle.
• In all of these genres, experience helps! Solving a lot of puzzles of a genre gives you a good feel for what is and what isn't possible, and how much certain clues constrain your result. If you're making a new genre or a new variant, you will likely need to experiment with the new rules to see how they work: I suggest starting with small puzzles to explore the 'basic' deductions of your rule set, and then try to look for more larger deductions you can force, using more clues together.

Happy constructing!

Answer 2

I'll describe one way. It is certainly not the only way, and often won't be the best.

Solving candidate puzzles

There is a fairly general technique that can be used to make a computer solve this kind of puzzle, called constraint propagation. It works like this:

First, you make a list of things that could be known about a solution. For instance: what number goes in such-and-such a cell? Or: Where is the "1" in such-and-such a row? Or: How many odd numbers are there in such-and-such a region? It's fine for these things to be redundant, in the sense that knowing the answers to some of them is enough to determine the answers to others. There need to be enough that if you know the answers to them all then you know the complete solution.

Now make a list of all the possible answers to each one. What we're going to do is to cut down these lists, bit by bit.

First of all, whatever facts are given as part of the puzzle will impose some restrictions. So, shorten all the lists that are affected by those facts. And mark them as having changed recently.

Now, repeatedly do the following: If one of those lists has been marked as changed, look at every other list whose entries might be affected by the change, and figure out what entries they should have now. If any of them have changed, mark 'em as having changed. Finally, remove the recently-changed mark on the list you were looking at.

(That's the "constraint propagation" step. The "constraints" are the facts of the form "the answer to this question is one of the things in this list", and every time one of these constraints tightens we "propagate" the results to other questions.)

Eventually, this process will stop making progress. At that point, if you're lucky the puzzle will be solved. If not, pick one of your lists and split it in two somehow. "The answer to question Q is either in list A or in list B." Then try solving the puzzle assuming list A, and try solving it assuming list B. (When you make either of those assumptions, you propagate constraints again, and then you may need to do further list-splitting.)

The above is a very partial description of what you need to do; there are lots of further details (how do you keep track of which things have changed? what order do you process things in? when you need to split a list, how do you split it? how do you cope if some of the lists are unmanageably long?) and they can make a big difference to how fast the process is.

So, anyway, you now have a machine that can take a puzzle and find solutions. If there are no solutions, it will say so. If there are multiple solutions, it will say so. (If you do exactly what I described above, it will find all of them. In some cases that may be a huge number. You can make it stop as soon as it finds more than one.)

Creating puzzles

Now you can create a puzzle as follows. Make a random one. Then repeat the following process: if it has no solutions, remove some of the information given to the solver; if it has multiple solutions, add some information (either completely at random, or by picking one of those solutions and adding some information that's true for that solution); if it has a unique solution, try removing information until you no longer have a unique solution.

Eventually this will give you a puzzle that has a unique solution but where none of the information supplied to the solver is unnecessary.

Why that might not be good enough

This doesn't guarantee, of course, that the puzzle isn't painful or boring to solve. (It may be that there's no feasible way other than "try lots of possibilities and see what works".) It doesn't guarantee that solving it benefits from any particular kind of cleverness. And it doesn't guarantee any of the nice aesthetic properties (symmetry, etc.) that you might want.

If you care about those things, then you need to do something more humanly creative. Other people will know much more about that than I do. (There might be an intermediate option. Create lots of puzzles automatically, as described above. Then try solving them by hand, and see if any of them are nice.)

Making easier puzzles

In principle, given enough time constraint propagation can solve any puzzle. If instead you use a solver that only knows how to apply a limited range of techniques, the puzzle-making process described above will deliver a puzzle that is only just solvable using those techniques. So you can e.g. make sudoku puzzles that can be solved just by repeatedly identifying a cell where only one number can go because all the others are already present in its row, column, or box.

Answer 3

While creating a grid-deduction puzzle, I believe you need two programmings:

1. A brute-force programming that solves the problem quickly and create randomly different puzzles which have unique solutions.
2. Another programming which behaves like a normal solver with lots of IFs in a specific order and check how long does it take to solve it and what IF conditions applied the most to find the level of difficulty.