1) It's not too hard to make a problem with at least one solution (just put the queens down first, then draw boxes), but there isn't any good way of making levels with unique solutions.
2) Once you've accomplished that, it's hard to predict how hard a level will be, and then it's hard to make levels easier / harder.
I happen to be currently researching this topic (well, I'm doing all kinds of these grid-based puzzles, but this is an example). The algorithm tries to make "good" levels, but there is a good probability it will end up with something useless we need to throw away, and then try again.
It's easy to make levels which are trivial, and similarly easy to make levels which are far beyond human ability, but hitting things in the 'human tricky but solvable' sweet-spot is where most of the difficulty comes from.
I should probably try writing up a human-readable version of how I do it. It involves a bunch of Rust code, so I can hit a whole bunch of trendy topics!
> I should probably try writing up a human-readable version of how I do it. It involves a bunch of Rust code, so I can hit a whole bunch of trendy topics!
Given that this could be a variant of "exact cover", using zdds to explore the problem space might simplify finding exact puzzles in addition to puzzles that require lookahead.
Generally what is needed is a subroutine that can tell you 1) if the problem has a solution, and 2) if the solution is unique (common requirement for puzzles like these). Using such a model as a sub-routine, a heuristic search can be done to gradually build up puzzles. If your solver technology of choice can handle quantified problems, that could be used to integrate those two problems into one, but that is quite a lot harder to to.
If the base solver you have is a system that can be run in various configurations with different levels of reasoning and assumption as well as a report on the amount of search needed if any, that can be very useful as a way to measure the hardness. In Sudoku as a Constraint problem (https://citeseerx.ist.psu.edu/document?doi=4f069d85116ab6b4c...), Helmut Simonis tested lots of 9x9 Sudoku puzzles against various levels of propagation and pre-processing as a way to measure the hardness of Sudoku puzzles by categorizing them by the level of reasoning needed to solve without search. The MiniZinc model for LinkedIn Queens (https://news.ycombinator.com/item?id=44353731) can be used with various solvers and levels of propagation as such a subroutine.
Now, for production-level puzzle making, such as what King does for Candy Crush, the problems and requirements are even harder. I've heard presentation where they talk about training neural networks to play like human testers, so not optimal play but most human like play, in order to test the hardness level of the puzzles.
It's the same problem as with generating good sudoku boards. It's not easy, and there's not many publicly available solutions, but solutions exist.
A common opinion is that a good board is solvable without the use of backtracking. A set of known techniques should be enough to solve the board. To validate if a board is "fun" you need to have a program that can solve the board using these known techniques. Making that program is much harder than just making a general solver. And then you need to find the boards that can be validated as fun. Either you search through random boards, or you get clever...
I've noticed that puzzles that can be solved with CP-SAT's presolver so that the SAT search does not even need to be invoked basically adhere to this (no backtracking, known rules), e.g.:
#Variables: 121 (91 primary variables)
- 121 Booleans in [0,1]
#kLinear1: 200 (#enforced: 200)
#kLinear2: 1
#kLinear3: 2
#kLinearN: 30 (#terms: 355)
Presolve summary:
- 1 affine relations were detected.
- rule 'affine: new relation' was applied 1 time.
- rule 'at_most_one: empty or all false' was applied 148 times.
- rule 'at_most_one: removed literals' was applied 148 times.
- rule 'at_most_one: satisfied' was applied 36 times.
- rule 'deductions: 200 stored' was applied 1 time.
- rule 'exactly_one: removed literals' was applied 2 times.
- rule 'exactly_one: satisfied' was applied 31 times.
- rule 'linear: empty' was applied 1 time.
- rule 'linear: fixed or dup variables' was applied 12 times.
- rule 'linear: positive equal one' was applied 31 times.
- rule 'linear: reduced variable domains' was applied 1 time.
- rule 'linear: remapped using affine relations' was applied 4 times.
- rule 'presolve: 120 unused variables removed.' was applied 1 time.
- rule 'presolve: iteration' was applied 2 times.
Presolved satisfaction model '': (model_fingerprint: 0xa5b85c5e198ed849)
#Variables: 0 (0 primary variables)
The solution hint is complete and is feasible.
#1 0.00s main
a a a a a a a a a a *A*
a a a b b b b *B* a a a
a a *C* b d d d b b a a
a c c d d *E* d d b b a
a c d *D* d e d d d b a
a f d d d e e e d *G* a
a *F* d d d d d d d g a
a f f d d d d d *H* g a
*I* i f f d d d h h a a
i i i f *J* j j j a a a
i i i i i k *K* j a a a
Together with validating that there is only 1 solution you would probably be able to make the search for good boards a more guided than random creation.
Simulated annealing with a difficulty heuristic (like minimum required logical steps) works well - start with a valid solution, then randomly modify colors while maintaining uniqueness.
That will produce challenging boards ?