6
$\begingroup$

The 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 puzzle?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

While creating a 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.
$\endgroup$

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.