I use Nooks for my paperback library (having finally come to
appreciate that media MORE than dead trees!ÿ :< )
I have many of them as it lets me read different things in
different places without having to lug one around with me.
Ditto for SWMBO.
And, for friends who want to "borrow a book" (something I always
dreaded with dead trees as you'd get the book back with a broken
spine, dog-eared pages, etc. -- sometimes even NOTES written inside!)
I can just copy whatever title(s) are desired onto the Nook and
admonish them not to forget where they got it!ÿ (i.e., this is a loan,
not a gift).
A neighbor called, excited to find *puzzles* on the Nook she'd borrowed.
I cautioned her that there were a limited number of crossword puzzles
(so, sooner or later, you will recognize one that you'd solved previously).
But, I *thought* the Sudoku puzzles were created on the fly (it's hard to recognize if you've already solved one, esp if they are prestored in
symbolic form whereby every 3 can be replaced with a 2 and a new APPEARING puzzle created).
Which got me thinking about how you would dynamically create such a puzzle, given that it would have to be solvable (algorithmically, not just by chance).
Which got me thinking of the tougher problem:ÿ creating a *crossword* from scratch!ÿ Without just relying on an exhaustive attempt to paste words from
a (constrained) glossary onto a grid.
I recall an adviser's relating how his son was so proud to have created
his first "symmetric" crossword so it's got to be a tedious task
"manually".
Especially for "themed" puzzles.
So, are the published puzzles (e.g., NYT) created by machine?ÿ Or, is someone
buzy with quadrille pads each week trying to get the puzzle ready for
NEXT week?
So, are the published puzzles (e.g., NYT) created by machine?ÿ Or, is someone
buzy with quadrille pads each week trying to get the puzzle ready for NEXT week?
Most decent crosswords in the broadsheets have particular named human setters
(using a pseudonym) that come with their own quirky style of clues. I expect they are born pattern matchers with a huge vocabulary.
The interlocking word pattern is machine solvable. Likewise you can index all
possible anagrams of a word or phrase into other words.
I expect that today they do have some computer assistance to find words that fit. When I was at school you had to do it by brute force.
Indeed it was sometimes a homework exercise in the English class with a given
pattern of blocked out squares.
I use Nooks for my paperback library (having finally come to
appreciate that media MORE than dead trees! :< )
I have many of them as it lets me read different things in
different places without having to lug one around with me.
Ditto for SWMBO.
And, for friends who want to "borrow a book" (something I always
dreaded with dead trees as you'd get the book back with a broken
spine, dog-eared pages, etc. -- sometimes even NOTES written inside!)
I can just copy whatever title(s) are desired onto the Nook and
admonish them not to forget where they got it! (i.e., this is a loan,
not a gift).
A neighbor called, excited to find *puzzles* on the Nook she'd borrowed.
I cautioned her that there were a limited number of crossword puzzles
(so, sooner or later, you will recognize one that you'd solved previously).
But, I *thought* the Sudoku puzzles were created on the fly (it's hard to recognize if you've already solved one, esp if they are prestored in
symbolic form whereby every 3 can be replaced with a 2 and a new APPEARING puzzle created).
Which got me thinking about how you would dynamically create such a puzzle, given that it would have to be solvable (algorithmically, not just by chance).
Which got me thinking of the tougher problem: creating a *crossword* from scratch! Without just relying on an exhaustive attempt to paste words from
a (constrained) glossary onto a grid.
Don Y <blockedofcourse@foo.invalid> wrote:
Which got me thinking about how you would dynamically create such a puzzle, >> given that it would have to be solvable (algorithmically, not just by chance).
AFAIK all Sudoku puzzles are algorithmically solvable, that is you
can check if there is a unique solution (and find a solution when
it exists).
So you may simply generate random sudoku and reject
ones that do not have unique solution. Slightly harder may
deciding how hard given sudoku is for people (you do not want them
too easy, but also you do not want ones that only computer
can solve).
Which got me thinking of the tougher problem: creating a *crossword* from >> scratch! Without just relying on an exhaustive attempt to paste words from >> a (constrained) glossary onto a grid.
AFAIK modern version of exhaustive search are much more efficient
than naive versions. I do not think that reasonably sized crossword
abd glossary would be a problem for them.
On 11/12/2026 8:15 AM, Waldek Hebisch wrote:
Don Y <blockedofcourse@foo.invalid> wrote:
Which got me thinking about how you would dynamically create such a puzzle, >>> given that it would have to be solvable (algorithmically, not just by chance).
AFAIK all Sudoku puzzles are algorithmically solvable, that is you
can check if there is a unique solution (and find a solution when
it exists).
That doesn't make for an *engaging* problem.
At one end of the spectrum, I can put three numbers on the grid and
leave the rest to the "player". A multitude of possible solutions
so their efforts are largely just time consuming with very low level
of reasoning.
At the other end, I can populate the grid *slectively* such that only
one solution is possible.
Yet, if arriving at that solution involves "taking a guess" at
any stage (because you can't deterministically rule out particular candidates), then it is far less fulfilling as you can "guess"
wrong and then have to backtrack to that point to "make the other
choice".
Here is just such a puzzle:
--7-1-2-5
--6----7-
9----7--1
-3----8--
--27---1-
8-135-7-6
----9613-
---------
2---3---8
You can unambiguously deduce every step in the completion of the grid
up to this point (spoiler alert):
--7-1-2-5
--6----7-
9----7--1
73----8--
--27---1-
8-135-7-6
---296137
xx3-7----
279-3---8
[I *think* this is the most resolved the puzzle can become but haven't
spent more than a few minutes examining its current state]
I know, for example, that one of the two X's will be either 1 or 6 and the other X would be the unchosen value. But, I can't reliably say WHICH is which. One "choice" will be incorrect. (and, there is no guarantee that
the refinement of valid choices that occurs AFTER such a choice won't
present another "choice situation").
But, hereafter, you have to "make a guess" as to which of the remaining "legal" moves are worth pursuing. If you are careful in your selection
of WHERE to make your guess, you can often reduce this to one of two
choices (only one of which will result in a solution). if you
guess wrong, then you have to backtrack your guesses from this point
and "take the other option" (assuming you only had two options
available).
[There are other "choice opportunities" on the board so another may be
more profitable in narrowing the potential subsequent choices]
This is disheartening as it relies on luck instead of deductive reasoning.
Sudoku differs from e.g., Solitaire in that one can *reason* the
choice to make at each step -- up to this point. With solitaire,
there is no easy way to look ahead to determine if your current
CHOICE is correct.
So you may simply generate random sudoku and reject
ones that do not have unique solution. Slightly harder may
deciding how hard given sudoku is for people (you do not want them
too easy, but also you do not want ones that only computer
can solve).
Exactly. What *criteria* does an algorithm use to create a puzzle
of a given complexity? How do you even MEASURE the compleity?
Is it simply a matter of the number of prefilled squares that are
presented to the player? Or, do the *choices* of those squares
significantly impact the difficulty level?
Or, is it easier to just PREcompute the set of potential puzzles
using symbolic representations of the numbers, select one at
random, apply rotation/flip transforms to further "randomize"
it and then bind digits to the symbols?? If the number of such
"templates" is small, then simply storing them might be more
efficient than generating them.
Which got me thinking of the tougher problem: creating a *crossword* from >>> scratch! Without just relying on an exhaustive attempt to paste words from >>> a (constrained) glossary onto a grid.
AFAIK modern version of exhaustive search are much more efficient
than naive versions. I do not think that reasonably sized crossword
abd glossary would be a problem for them.
You don't do an exhaustive search as you have the same "clues" that a crossword solver would have.
E.g., weed out all words that are shorter or longer than the shortest unsolved clue (repeat throughout the solving stage).
For any given clue, use the existing "filled squares" to condition the
words that you examine ("seven letters, first letter must be an L, 5th
letter must be a P, etc."). You can index the choices so you don't
have to sequentially examine a lost of potentially thousands of
words looking for candidates (current conditions always get tighter,
until you have to backup, so the lists always get shorter)
And, if you are creating a puzzle, then you try "candidate N from "list
of candidates X /for this clue/ before advancing to pick a candidate for
the next clue. If you complete the last clue, you are done. Otherwise, anytime you exhaust a list of candidates for a particular clue, you
"backup" to the previous clue, invalidate its current choice and advance
to the next choice available to it, repeating as necessary.
[Of course, duality ensures this can be recursive or iterative solution
based on your preference and how much housekeeping you want to do]
Don Y <blockedofcourse@foo.invalid> wrote:
On 11/12/2026 8:15 AM, Waldek Hebisch wrote:
Don Y <blockedofcourse@foo.invalid> wrote:
Which got me thinking about how you would dynamically create such a puzzle,
given that it would have to be solvable (algorithmically, not just by chance).
AFAIK all Sudoku puzzles are algorithmically solvable, that is you
can check if there is a unique solution (and find a solution when
it exists).
That doesn't make for an *engaging* problem.
At one end of the spectrum, I can put three numbers on the grid and
leave the rest to the "player". A multitude of possible solutions
so their efforts are largely just time consuming with very low level
of reasoning.
At the other end, I can populate the grid *slectively* such that only
one solution is possible.
Yet, if arriving at that solution involves "taking a guess" at
any stage (because you can't deterministically rule out particular
candidates), then it is far less fulfilling as you can "guess"
wrong and then have to backtrack to that point to "make the other
choice".
Here is just such a puzzle:
--7-1-2-5
--6----7-
9----7--1
-3----8--
--27---1-
8-135-7-6
----9613-
---------
2---3---8
You can unambiguously deduce every step in the completion of the grid
up to this point (spoiler alert):
--7-1-2-5
--6----7-
9----7--1
73----8--
--27---1-
8-135-7-6
---296137
xx3-7----
279-3---8
[I *think* this is the most resolved the puzzle can become but haven't
spent more than a few minutes examining its current state]
One can easiliy deduce more:
--7-1-2-5
--6----7-
9----73-1
73----8--
--27---1-
8-135-7-6
---296137
--3-7----
279-3---8
and several steps beyond that. As one point I did a binary
guess, I guessed correctly and after that I got a solution.
Actually, at later step I made a mistake, so I tried the
other possiblity which led me to contradiction. Consequently
I suspected that this may be a "bad" sudoku, without
solution. But I created a solver and it found solution.
Comparing I fund place where I made an error and restarting
from this place I got solution.
Solver tells me that it need 2 binary decisions, which is
more than my "by hand way". I am not sure why solver
needed more decisions, it could be because the solver
uses generic method, while I used technique specific
to sudoku which possibly could eliminated one decision
point. In fact, I do not know if guessing was needed,
it is possible that I overlooked some reasoning that
would allow progress without guessing.
I know, for example, that one of the two X's will be either 1 or 6 and the >> other X would be the unchosen value. But, I can't reliably say WHICH is
which. One "choice" will be incorrect. (and, there is no guarantee that
the refinement of valid choices that occurs AFTER such a choice won't
present another "choice situation").
But, hereafter, you have to "make a guess" as to which of the remaining
"legal" moves are worth pursuing. If you are careful in your selection
of WHERE to make your guess, you can often reduce this to one of two
choices (only one of which will result in a solution). if you
guess wrong, then you have to backtrack your guesses from this point
and "take the other option" (assuming you only had two options
available).
[There are other "choice opportunities" on the board so another may be
more profitable in narrowing the potential subsequent choices]
This is disheartening as it relies on luck instead of deductive reasoning. >>
Sudoku differs from e.g., Solitaire in that one can *reason* the
choice to make at each step -- up to this point. With solitaire,
there is no easy way to look ahead to determine if your current
CHOICE is correct.
So you may simply generate random sudoku and reject
ones that do not have unique solution. Slightly harder may
deciding how hard given sudoku is for people (you do not want them
too easy, but also you do not want ones that only computer
can solve).
Exactly. What *criteria* does an algorithm use to create a puzzle
of a given complexity? How do you even MEASURE the compleity?
Is it simply a matter of the number of prefilled squares that are
presented to the player? Or, do the *choices* of those squares
significantly impact the difficulty level?
I would say that difficulty depends on complexity of algorithm
needed to solve it. Basicaly anybody can to simple
propagation, if it leads to solution, then the sudoku is
easy. If more complex propagation rules are needed, then
it is harder. People seem to be quite reluctant to
systematically check alternatives, but if number of
alternatives is small, than IMO the sudoku is stil
reasonable. Of course, people that know only simple
propagation may be forced to check alternatives in
cases where better propagation rules would lead to
unique possibility.
Number of prefilled squares determines number of squares
to fill, so in a sense amount of work, but otherwise
I do not think that corelation with difficulty is
very strong.
Or, is it easier to just PREcompute the set of potential puzzles
using symbolic representations of the numbers, select one at
random, apply rotation/flip transforms to further "randomize"
it and then bind digits to the symbols?? If the number of such
"templates" is small, then simply storing them might be more
efficient than generating them.
I am not sure how much effort is needed for generation. Solver
solves your one in less than 2ms. Similarly, starting from
empty square (of course in such case there are multiple
solution, but solver produces just one of them). So, one
can make several solution attempts, changing candidate
sudoku for better properties and still have subsecond
generation time.
Which got me thinking of the tougher problem: creating a *crossword* from >>>> scratch! Without just relying on an exhaustive attempt to paste words from
a (constrained) glossary onto a grid.
AFAIK modern version of exhaustive search are much more efficient
than naive versions. I do not think that reasonably sized crossword
abd glossary would be a problem for them.
You don't do an exhaustive search as you have the same "clues" that a
crossword solver would have.
E.g., weed out all words that are shorter or longer than the shortest
unsolved clue (repeat throughout the solving stage).
I am not sure what you want to say here. Of course you need
some lingustic knowledge in form of word list and for each
word you need possible questions/clues. You may wish some
form of semantic markup if you aim at specific theme.
But otherwise this is problem of putting words on a grid
satisfying some constraints. Eliminating possibilities
that "obviously" do not lead to solution is standard part
of modern exhaustive search. Modern methods are quite
good at doing it in generic way (that is using only
information from problem formulation). But if you need
to optimize more you can try tweaking algorithm to
your specific problem.
For any given clue, use the existing "filled squares" to condition the
words that you examine ("seven letters, first letter must be an L, 5th
letter must be a P, etc."). You can index the choices so you don't
have to sequentially examine a lost of potentially thousands of
words looking for candidates (current conditions always get tighter,
until you have to backup, so the lists always get shorter)
And, if you are creating a puzzle, then you try "candidate N from "list
of candidates X /for this clue/ before advancing to pick a candidate for
the next clue. If you complete the last clue, you are done. Otherwise,
anytime you exhaust a list of candidates for a particular clue, you
"backup" to the previous clue, invalidate its current choice and advance
to the next choice available to it, repeating as necessary.
[Of course, duality ensures this can be recursive or iterative solution
based on your preference and how much housekeeping you want to do]
On 11/14/2026 9:08 PM, Waldek Hebisch wrote:
Don Y <blockedofcourse@foo.invalid> wrote:
On 11/12/2026 8:15 AM, Waldek Hebisch wrote:
Don Y <blockedofcourse@foo.invalid> wrote:
Which got me thinking about how you would dynamically create such a puzzle,
given that it would have to be solvable (algorithmically, not just by chance).
AFAIK all Sudoku puzzles are algorithmically solvable, that is you
can check if there is a unique solution (and find a solution when
it exists).
That doesn't make for an *engaging* problem.
At one end of the spectrum, I can put three numbers on the grid and
leave the rest to the "player". A multitude of possible solutions
so their efforts are largely just time consuming with very low level
of reasoning.
At the other end, I can populate the grid *slectively* such that only
one solution is possible.
Yet, if arriving at that solution involves "taking a guess" at
any stage (because you can't deterministically rule out particular
candidates), then it is far less fulfilling as you can "guess"
wrong and then have to backtrack to that point to "make the other
choice".
Here is just such a puzzle:
--7-1-2-5
--6----7-
9----7--1
-3----8--
--27---1-
8-135-7-6
----9613-
---------
2---3---8
You can unambiguously deduce every step in the completion of the grid
up to this point (spoiler alert):
--7-1-2-5
--6----7-
9----7--1
73----8--
--27---1-
8-135-7-6
---296137
xx3-7----
279-3---8
[I *think* this is the most resolved the puzzle can become but haven't
spent more than a few minutes examining its current state]
One can easiliy deduce more:
--7-1-2-5
--6----7-
9----73-1
73----8--
--27---1-
8-135-7-6
---296137
--3-7----
279-3---8
--7-1-2-5
--6----7-
9----73-1
73----8--
--27---13
8-135-7-6
---296137
--3-7----
279-3-6-8
But, at that point, you have to make a guess.
And, have to carefully consider WHERE you make that guess
if you don't want to end up having to make ANOTHER guess.
I don't consider puzzles that rely on guesswork to be
particularly appealing as you can rationalize not doing ANY
deductive work and just guessing at the whole thing!
and several steps beyond that. As one point I did a binary
guess, I guessed correctly and after that I got a solution.
Actually, at later step I made a mistake, so I tried the
other possiblity which led me to contradiction. Consequently
Exactly. But, then you have to "backup". Easy for a machine
algorithm but a lot harder to do "in your head"
I suspected that this may be a "bad" sudoku, without
solution. But I created a solver and it found solution.
Comparing I fund place where I made an error and restarting
from this place I got solution.
IME, all of the puzzles have been solvable. But, often require
a guess.
Minesweeper is similarly annoying as some puzzles resolve to a
point where you can't unambiguously determine the next "safe"
square.
This is disappointing as you've invested time and been screwed through
no fault or deficiency of your own.
So you may simply generate random sudoku and reject
ones that do not have unique solution. Slightly harder may
deciding how hard given sudoku is for people (you do not want them
too easy, but also you do not want ones that only computer
can solve).
Exactly. What *criteria* does an algorithm use to create a puzzle
of a given complexity? How do you even MEASURE the compleity?
Is it simply a matter of the number of prefilled squares that are
presented to the player? Or, do the *choices* of those squares
significantly impact the difficulty level?
I would say that difficulty depends on complexity of algorithm
needed to solve it. Basicaly anybody can to simple
propagation, if it leads to solution, then the sudoku is
easy. If more complex propagation rules are needed, then
it is harder. People seem to be quite reluctant to
systematically check alternatives, but if number of
alternatives is small, than IMO the sudoku is stil
reasonable. Of course, people that know only simple
propagation may be forced to check alternatives in
cases where better propagation rules would lead to
unique possibility.
Number of prefilled squares determines number of squares
to fill, so in a sense amount of work, but otherwise
I do not think that corelation with difficulty is
very strong.
But, as this program has difficulty levels, it has used
SOME criteria to determine how to create suitable puzzles.
Or, is it easier to just PREcompute the set of potential puzzles
using symbolic representations of the numbers, select one at
random, apply rotation/flip transforms to further "randomize"
it and then bind digits to the symbols?? If the number of such
"templates" is small, then simply storing them might be more
efficient than generating them.
I am not sure how much effort is needed for generation. Solver
solves your one in less than 2ms. Similarly, starting from
empty square (of course in such case there are multiple
solution, but solver produces just one of them). So, one
can make several solution attempts, changing candidate
sudoku for better properties and still have subsecond
generation time.
The issue is identifying the criteria that one can use to
determine "deterministic" solvability when *creating* the
puzzle. With a crossword, it is obvious that a created
puzzle is solvable because you created it in its solved state
and the clues are supposedly correctly associated with each
entry.
Which got me thinking of the tougher problem: creating a *crossword* from
scratch! Without just relying on an exhaustive attempt to paste words from
a (constrained) glossary onto a grid.
AFAIK modern version of exhaustive search are much more efficient
than naive versions. I do not think that reasonably sized crossword
abd glossary would be a problem for them.
You don't do an exhaustive search as you have the same "clues" that a
crossword solver would have.
E.g., weed out all words that are shorter or longer than the shortest
unsolved clue (repeat throughout the solving stage).
I am not sure what you want to say here. Of course you need
some lingustic knowledge in form of word list and for each
word you need possible questions/clues. You may wish some
form of semantic markup if you aim at specific theme.
The mechanistic way of fitting words to a grid is easy.
There are optimizations you can use to keep pruning the list
of available "candidates" to place into the puzzle.
But, the harder problem is how those words map back to their
clues.
The crossword app in the Nook lets you choose
difficulty level, themeless, etc.
Some of the difficulty lies in creating ambiguous clues;
clues that suggest one word but actually mean another
(often playing on different parts of speech, etc.)
But, when you want to tie the clues (and solution words)
together in a theme, that limits the clues you can offer
and the words to which they reduce.
I don't see an easy way to impose these criteria
algorithmically. How do you decide on a theme? How
do you rationalize a solution as being consistent with
that theme?
There is old puzzle of 15. You have 4 by 4 grid and movable
squares with numbers from 1 to 15 fitted into it. One
square is empty and you can move any neighbouring movable
square into the empty position, in effect exchanging empty
square with one of the neighbours. The goal it to put
squares in order. But there are to classes of positions,
one class which can be ordered and the second one where the
best you can do is to get at distance of one exchange to
the ordered state. Apparently, all puzzles are sold in
unsolvable position. OK, all such puzles (a few) that I
got in my hand were in such state. One can disassemble
the puzzle and put it back in another state, but I doubt
the users did it. Rather, I think that manufacturers
decided that they can sell more selling them in unsolvable
state.
--7-1-2-5
--6----7-
9----73-1
73----8--
--27---13
8-135-7-6
---296137
--3-7----
279-3-6-8
But, at that point, you have to make a guess.
No, I can get at least to:
--791-265
--6----7-
9----7381
73----8--
--27---13
8-135-7-6
--8296137
--3-7----
279-3-6-8
At this point I have a lot of extra information, but I do not
know if this information is enough to find next square
(my single guess was made at this point). Solver tells me
that starting from this it still needs 2 decisions, when
I give it the next (guessed) state it say that it needs
1 decision. So simple propagation will not work, but
more complex rules may work (as apparently happens with
the second decision point, which solver needs, but I do
not need).
And, have to carefully consider WHERE you make that guess
if you don't want to end up having to make ANOTHER guess.
I don't consider puzzles that rely on guesswork to be
particularly appealing as you can rationalize not doing ANY
deductive work and just guessing at the whole thing!
Well, if you are too eager to make guesses, then you are
likely to spend a lot of time pursuing wrong paths.
Consequently, you are unlikely to find solution in
reasonable time.
and several steps beyond that. As one point I did a binary
guess, I guessed correctly and after that I got a solution.
Actually, at later step I made a mistake, so I tried the
other possiblity which led me to contradiction. Consequently
Exactly. But, then you have to "backup". Easy for a machine
algorithm but a lot harder to do "in your head"
I was not doing it in my head. I have kept copies of
the state after making a move (or a few if they were
obiously related). I did it in a computer file, but
the same would also work on the paper (given sufficient
supply of scratch paper). So backtracking itself is not
hard. The problem is amount of work you need to do
if you backtrack too eagerly.
I suspected that this may be a "bad" sudoku, without
solution. But I created a solver and it found solution.
Comparing I fund place where I made an error and restarting
from this place I got solution.
IME, all of the puzzles have been solvable. But, often require
a guess.
Minesweeper is similarly annoying as some puzzles resolve to a
point where you can't unambiguously determine the next "safe"
square.
I think it is supposed to be a feature. If you make too many
guesses you will sooner or later hit a mine and loose. Minimizing
guesses siginficantly increases chance of winning.
This is disappointing as you've invested time and been screwed through
no fault or deficiency of your own.
Goal of creators usually is not pure satisfaction of users.
Rather, they want you to come for more. If you win every
time than you will quickly become bored. OTOH "I almost
made it" encourages another trial.
There is old puzzle of 15. You have 4 by 4 grid and movable
squares with numbers from 1 to 15 fitted into it. One
square is empty and you can move any neighbouring movable
square into the empty position, in effect exchanging empty
square with one of the neighbours. The goal it to put
squares in order. But there are to classes of positions,
one class which can be ordered and the second one where the
best you can do is to get at distance of one exchange to
the ordered state. Apparently, all puzzles are sold in
unsolvable position. OK, all such puzles (a few) that I
got in my hand were in such state. One can disassemble
the puzzle and put it back in another state, but I doubt
the users did it. Rather, I think that manufacturers
decided that they can sell more selling them in unsolvable
state.
So you may simply generate random sudoku and reject
ones that do not have unique solution. Slightly harder may
deciding how hard given sudoku is for people (you do not want them
too easy, but also you do not want ones that only computer
can solve).
Exactly. What *criteria* does an algorithm use to create a puzzle
of a given complexity? How do you even MEASURE the compleity?
Is it simply a matter of the number of prefilled squares that are
presented to the player? Or, do the *choices* of those squares
significantly impact the difficulty level?
I would say that difficulty depends on complexity of algorithm
needed to solve it. Basicaly anybody can to simple
propagation, if it leads to solution, then the sudoku is
easy. If more complex propagation rules are needed, then
it is harder. People seem to be quite reluctant to
systematically check alternatives, but if number of
alternatives is small, than IMO the sudoku is stil
reasonable. Of course, people that know only simple
propagation may be forced to check alternatives in
cases where better propagation rules would lead to
unique possibility.
Number of prefilled squares determines number of squares
to fill, so in a sense amount of work, but otherwise
I do not think that corelation with difficulty is
very strong.
But, as this program has difficulty levels, it has used
SOME criteria to determine how to create suitable puzzles.
As I wrote, you can judge difficulty based on rules
needed to solve it and beyond that by number of decision
points. Concerning methods, in several situations random
generation works well to produce varied objects. You
may need to think about good distribution, for example
I use random generation of expressions, but my first
attempts tended to produce expressions with undesirable
characteristics. Later, I learned about better
distribution.
Or, is it easier to just PREcompute the set of potential puzzles
using symbolic representations of the numbers, select one at
random, apply rotation/flip transforms to further "randomize"
it and then bind digits to the symbols?? If the number of such
"templates" is small, then simply storing them might be more
efficient than generating them.
I am not sure how much effort is needed for generation. Solver
solves your one in less than 2ms. Similarly, starting from
empty square (of course in such case there are multiple
solution, but solver produces just one of them). So, one
can make several solution attempts, changing candidate
sudoku for better properties and still have subsecond
generation time.
The issue is identifying the criteria that one can use to
determine "deterministic" solvability when *creating* the
puzzle. With a crossword, it is obvious that a created
puzzle is solvable because you created it in its solved state
and the clues are supposedly correctly associated with each
entry.
I am not sure why you repeat "when creating". You can
generate first and discard bad ones later. Or, if that
is too expensive you can mutate generated bad case till
it is satisfactory.
E.g., weed out all words that are shorter or longer than the shortest
unsolved clue (repeat throughout the solving stage).
I am not sure what you want to say here. Of course you need
some lingustic knowledge in form of word list and for each
word you need possible questions/clues. You may wish some
form of semantic markup if you aim at specific theme.
The mechanistic way of fitting words to a grid is easy.
There are optimizations you can use to keep pruning the list
of available "candidates" to place into the puzzle.
But, the harder problem is how those words map back to their
clues.
I suppose that this is done via precomputed table. I guess
that in old times crossword makers had a list of words,
maybe as explict set of cards, maybe implicity as content
of dictionaries and similar works on their bookshelf.
In modern times you could try to create needed table using
data mining combined with available language resources like
WordNet.
The crossword app in the Nook lets you choose
difficulty level, themeless, etc.
Some of the difficulty lies in creating ambiguous clues;
clues that suggest one word but actually mean another
(often playing on different parts of speech, etc.)
I guess now LLM could help with this, but in the past this
probably needed human work.
But, when you want to tie the clues (and solution words)
together in a theme, that limits the clues you can offer
and the words to which they reduce.
I don't see an easy way to impose these criteria
algorithmically. How do you decide on a theme? How
do you rationalize a solution as being consistent with
that theme?
AFAICS this is play with probabilities. I the past humans
would provide marked data, now there are data mining
techniques and LLM-s. Doing this needs a lot of raw
data and a lot of compute power, so an app almost
surely uses precomputed tables.
On 11/15/2026 7:13 AM, Waldek Hebisch wrote:
--7-1-2-5
--6----7-
9----73-1
73----8--
--27---13
8-135-7-6
---296137
--3-7----
279-3-6-8
But, at that point, you have to make a guess.
No, I can get at least to:
--791-265
--6----7-
9----7381
73----8--
--27---13
8-135-7-6
--8296137
--3-7----
279-3-6-8
The difference between your state and mine resolves to:
---9---6-
---------
-------8-
---------
---------
---------
--8------
---------
---------
suggesting you deduced one of these moves could be reasoned
from the current state of the solution WITHOUT GUESSING.
I don't see that to be the case (but, if I am wrong, you can
indicate which was the "next" move that you reasoned after
my state).
So you may simply generate random sudoku and reject
ones that do not have unique solution. Slightly harder may
deciding how hard given sudoku is for people (you do not want them >>>>>> too easy, but also you do not want ones that only computer
can solve).
Exactly. What *criteria* does an algorithm use to create a puzzle
of a given complexity? How do you even MEASURE the compleity?
Is it simply a matter of the number of prefilled squares that are
presented to the player? Or, do the *choices* of those squares
significantly impact the difficulty level?
I would say that difficulty depends on complexity of algorithm
needed to solve it. Basicaly anybody can to simple
propagation, if it leads to solution, then the sudoku is
easy. If more complex propagation rules are needed, then
it is harder. People seem to be quite reluctant to
systematically check alternatives, but if number of
alternatives is small, than IMO the sudoku is stil
reasonable. Of course, people that know only simple
propagation may be forced to check alternatives in
cases where better propagation rules would lead to
unique possibility.
Number of prefilled squares determines number of squares
to fill, so in a sense amount of work, but otherwise
I do not think that corelation with difficulty is
very strong.
But, as this program has difficulty levels, it has used
SOME criteria to determine how to create suitable puzzles.
As I wrote, you can judge difficulty based on rules
needed to solve it and beyond that by number of decision
I suspect the criteria actually implemented aren't that sophisticated;
more probably, "reveal X cells" where X decreases with difficulty
(providing less deductible constraint for the player)
points. Concerning methods, in several situations random
generation works well to produce varied objects. You
may need to think about good distribution, for example
I use random generation of expressions, but my first
attempts tended to produce expressions with undesirable
characteristics. Later, I learned about better
distribution.
Or, is it easier to just PREcompute the set of potential puzzles
using symbolic representations of the numbers, select one at
random, apply rotation/flip transforms to further "randomize"
it and then bind digits to the symbols?? If the number of such
"templates" is small, then simply storing them might be more
efficient than generating them.
I am not sure how much effort is needed for generation. Solver
solves your one in less than 2ms. Similarly, starting from
empty square (of course in such case there are multiple
solution, but solver produces just one of them). So, one
can make several solution attempts, changing candidate
sudoku for better properties and still have subsecond
generation time.
The issue is identifying the criteria that one can use to
determine "deterministic" solvability when *creating* the
puzzle. With a crossword, it is obvious that a created
puzzle is solvable because you created it in its solved state
and the clues are supposedly correctly associated with each
entry.
I am not sure why you repeat "when creating". You can
generate first and discard bad ones later. Or, if that
is too expensive you can mutate generated bad case till
it is satisfactory.
It seems the best approach is to generate a solution and
then decide how much of it to *reveal* to the player,
based on his level of difficulty. After all, you have
to be able to generate *a* solution for the puzzle.
E.g., weed out all words that are shorter or longer than the shortest >>>>> unsolved clue (repeat throughout the solving stage).
I am not sure what you want to say here. Of course you need
some lingustic knowledge in form of word list and for each
word you need possible questions/clues. You may wish some
form of semantic markup if you aim at specific theme.
The mechanistic way of fitting words to a grid is easy.
There are optimizations you can use to keep pruning the list
of available "candidates" to place into the puzzle.
But, the harder problem is how those words map back to their
clues.
I suppose that this is done via precomputed table. I guess
that in old times crossword makers had a list of words,
maybe as explict set of cards, maybe implicity as content
of dictionaries and similar works on their bookshelf.
In an automated solution, I would just tag each word with
criteria that the "designer" could use as filters.
E.g., "baseball" seems a common theme in many crosswords
that I've solved. So, I would tag words associated with
baseball with "#baseball" and would bias the algorithm to
select those over "non-baseball" words.
The actual clues associated with each word would be more difficult
to predefine as the theme can let you bias the clues to make
the solution easier or more difficult (at your perogative).
But, I think -- given a completed grid -- a human could exploit
his creativity to fabricate an appropriate set of clues, having
the "fitting" already handled for him.
In modern times you could try to create needed table using
data mining combined with available language resources like
WordNet.
The crossword app in the Nook lets you choose
difficulty level, themeless, etc.
Some of the difficulty lies in creating ambiguous clues;
clues that suggest one word but actually mean another
(often playing on different parts of speech, etc.)
I guess now LLM could help with this, but in the past this
probably needed human work.
But, when you want to tie the clues (and solution words)
together in a theme, that limits the clues you can offer
and the words to which they reduce.
I don't see an easy way to impose these criteria
algorithmically. How do you decide on a theme? How
do you rationalize a solution as being consistent with
that theme?
AFAICS this is play with probabilities. I the past humans
would provide marked data, now there are data mining
techniques and LLM-s. Doing this needs a lot of raw
data and a lot of compute power, so an app almost
surely uses precomputed tables.
Humans are needed to create ORIGINAL puzzles -- themes
that may not have been tried, word combinations, etc.
(when I was a kid, crosswords were prohibited from having
anything more than single word answers)
And, to create "cleverer" clues that rely on puns, etc.
instead of simple dictionary definitions.
I made a mistake in my reasoning, so my movements were not
fully justified. I created a propagation program and it
get to the point but can not move beyond what you get.
This is probably not most powerful propagation program,
but I doubt that better normal propagation rules would
help.
OTOH one can claim that single binary decision is rally not
guessing. Several so called "advanced strategies" look for
promising places subject to binary decision and egzamine
consequences of both alternatives. More precisely, for
each square of the grid one notes possible numbers in this
square. When trying one alternative you propagete info
getting tightened possibilites. Then you try the second
alternative and propagate info. Then you form logical
sum of the two alternatives. If it is more restrictive
then the starting state you made a progress. Different
advanced strategies differ in their choice of decision
and on amout of propagation that is performed. In a
sense ultimate advanced strategy would try any
possible binary decision and fully propagate consquences.
The case when sudoku is solved by propagatin after a
single decision is just a simple case of advanced strategy.
In general, after making progress you need to continue
with solution process. Note that whan using advanced
strategies you temporarily have two candidates for
partial solution, but never more than two. IIUC
published hard sudokus are usually not solvable just
using normal propagation, you are supposed to use
some advanced strategy, possibly multiple times.
I think that there exist sudokus that are not solvable
by any advanced strategy like above (that depending
only on binary choice).
So gessing (or recursive search) is really needed when
you need to deal simultaneousy with larger number of
possibilities.
<snip>
As I wrote, you can judge difficulty based on rules
needed to solve it and beyond that by number of decision
I suspect the criteria actually implemented aren't that sophisticated;
more probably, "reveal X cells" where X decreases with difficulty
(providing less deductible constraint for the player)
You can look at:
https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf
It claims approach that I suggested. Also older systems
like 'serate' claim to use method of this sort.
It seems the best approach is to generate a solution and
then decide how much of it to *reveal* to the player,
based on his level of difficulty. After all, you have
to be able to generate *a* solution for the puzzle.
Maybe. The paper above claim approach of this sort.
But usual convention seem to be to pubish minimal sudokus,
that is when you remove any of the clues then solution
is no longer unique. It seems that when you try to
build easily solvable sudoku you may get stuck with
nonminimal sudoku that can not be turned into easily
solvable one with smaller number of cues. So you
probaly need either recursive search for easily
solvable ones or generate randomly and filter on
difficulty.
AFAICS this is play with probabilities. I the past humans
would provide marked data, now there are data mining
techniques and LLM-s. Doing this needs a lot of raw
data and a lot of compute power, so an app almost
surely uses precomputed tables.
Humans are needed to create ORIGINAL puzzles -- themes
that may not have been tried, word combinations, etc.
(when I was a kid, crosswords were prohibited from having
anything more than single word answers)
And, to create "cleverer" clues that rely on puns, etc.
instead of simple dictionary definitions.
I suspect that now relativly small LLMs can do this. After
all that is really core functionality of LLMs, they produce
text that is likely in context of earlier text. So if
you provide a few examples and a word, then LLM should be able
to produce new clue fitting to the word and to the style
and theme of earlier example clues.
Now, if you do _not_ want accidental puns and want strict
adherence to scientific knowledge, then it get more
tricky. Also, censorship to avoid racist/sexist content
looks tricky.
| Sysop: | Jacob Catayoc |
|---|---|
| Location: | Pasay City, Metro Manila, Philippines |
| Users: | 5 |
| Nodes: | 4 (0 / 4) |
| Uptime: | 498678:02:02 |
| Calls: | 212 |
| Calls today: | 3 |
| Files: | 912 |
| D/L today: |
31 files (22,593K bytes) |
| Messages: | 69,856 |