I use Nooks for my paperback library (having finally come to
appreciate that media MORE than dead trees!-a :< )
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!-a (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:-a creating a *crossword* from scratch!-a 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?-a 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?-a 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.
| Sysop: | Amessyroom |
|---|---|
| Location: | Fayetteville, NC |
| Users: | 76 |
| Nodes: | 6 (0 / 6) |
| Uptime: | 55:57:06 |
| Calls: | 1,265 |
| Calls today: | 1 |
| Files: | 1,362 |
| D/L today: |
3 files (2,684K bytes) |
| Messages: | 285,712 |