• Puzzles

    From Don Y@3:633/10 to All on Monday, November 09, 2026 15:13:37
    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?

    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Martin Brown@3:633/10 to All on Tuesday, November 10, 2026 10:02:18
    On 09/11/2026 22:13, Don Y wrote:
    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).

    For sudoku (and killer sudoku) it can be fairly easily automated
    (although that doesn't prevent the odd one with an ambiguity from
    getting out into the wild). I've seen a few over the years.

    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?

    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.

    --
    Martin Brown


    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Don Y@3:633/10 to All on Wednesday, November 11, 2026 14:31:52
    On 11/10/2026 3:02 AM, Martin Brown wrote:
    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.

    Yeah, I looked at what would be required of an algorithm. Fitting "words" (letter sequences) to templates where some number of existing letter
    positions may have been defined is relatively easy (though computationally expensive, depending on size of glossary, "clues", etc.)

    But, what is missing it the "given clue" side; I can fit words but can't necessarily ensure that their clues (even if I *had* them) would fit a particular theme, etc. (e.g., baseball seems to be a common theme!)

    The interlocking word pattern is machine solvable. Likewise you can index all
    possible anagrams of a word or phrase into other words.

    It is relatively straightforward -- but, you have to exploit the fact that
    the "word list" is const else the computational/storage requirments explode! (my first approach passed a list of candidate words to each "clue fitting iteration" much like one would do in LISP; this consumed memory at a prodigious rate!)

    A more economical approach is to use a bit (bool) array to indicate the candidate words to be examined in a given iteration. So, you pass a bit
    per word per clue instead of the entire list of eligible 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.

    I suspect it is a matter of scale. Larger grids give more opportunities.
    But, also present more constraints.

    Indeed it was sometimes a homework exercise in the English class with a given
    pattern of blocked out squares.

    Similar in principle to a magic square.

    I'll look at the sudoku problem, next, as that seems orders of magnitude simpler. (It would be educational to discover how many *different*
    sudoku grids exist as it is likely a small number -- sort of like tic-tac-toe/noughts-and-crosses)

    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Waldek Hebisch@3:633/10 to All on Thursday, November 12, 2026 15:15:23
    Don Y <blockedofcourse@foo.invalid> wrote:
    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).

    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.

    --
    Waldek Hebisch

    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Don Y@3:633/10 to All on Thursday, November 12, 2026 16:11:49
    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]

    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Waldek Hebisch@3:633/10 to All on Sunday, November 15, 2026 04:08:11
    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]

    --
    Waldek Hebisch

    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Don Y@3:633/10 to All on Saturday, November 14, 2026 22:54:56
    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.

    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.

    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?

    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]



    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Waldek Hebisch@3:633/10 to All on Sunday, November 15, 2026 14:13:59
    Don Y <blockedofcourse@foo.invalid> wrote:
    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.

    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.

    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.

    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.

    --
    Waldek Hebisch

    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Johann 'Myrkraverk' Oskarsson@3:633/10 to All on Sunday, November 15, 2026 22:30:03
    On 11/15/2026 10:13 PM, Waldek Hebisch wrote:
    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.

    I had one of these as a kid. I came up an algorithm to always end up
    with the picture correct. Mine was a picture, and not numbers, but the algorithm is still the same -- assuming we're talking about the same
    puzzle.

    After coming up with the algorithm it was trivial but tedious to solve
    any of these -- I suppose I still remember it -- no matter how large the
    grid is. It's the last few pieces that most people struggle with, and
    it's "easy" to end up with an unsolvable situation and give up.

    Thank you, because now I remember the -- probably -- first algorithm I
    came up with on my own. That was before I learned how to use computers.

    I didn't spell out the algorithm, because I believe most people find
    these more fun if they don't know the solution. And other people in sci.electronics.design may want to exercise the gray cells and see if
    they discover it on their own.
    --
    Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
    I'm not from the Internet, I just work there. | via Easynews.com https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;
    Federated at https://fed.brid.gy/bsky/myrkraverk.bsky.social

    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Don Y@3:633/10 to All on Tuesday, November 17, 2026 17:35:10
    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).

    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).

    I regard my state as requiring a guess. The correct guess
    is to select '4' as the choice for the upper left corner
    of the upper left 3x3 grid. This unambiguously resolves to:

    487913265
    316825974
    925647381
    734162859
    652789413
    891354726
    548296137
    163478592
    279531648

    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.

    I make a guess when (and only when) there are no unambiguous
    deductions available.

    In an attempt to minimize the number of possible wrong guesses
    that may be required, I examine those cells for which only two
    choices exist (a cell with a single choice would be obvious;
    a cell with 8 choices would leave me wondering which of those
    8 to try first... second... third...)

    In this case, the possible choices (for the indicated cell)
    were 3 and 4. If I had picked 3, the solution would have
    progressed to a contradictory state *or* a state that
    required yet another guess (I got lucky so I don't know what
    '3' would actually have led to)

    But, this is an annoying approach to the problem, comparable
    to just throwing guesses at a poorly constrained grid. There's
    no satisfaction from having *worked* through to the answer.
    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.

    Unambiguous deductions are easy to follow through with.
    When you get to a point where a "choice" is required,
    then things fall to a sort of intuition -- recognizing
    patterns of "remaining candidates" in the indeterminate
    cells and using that to bias your choice of WHICH cell
    to exercise and which VALUE to pick, first.

    There is no guarantee that this will yield a successful
    result. But, it is a strategy that *hopes* to leave you
    facing a series of potentially incorrect "guesses" for
    a cell with lots of candidates.

    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.

    The first move in Minesweeper is always a guess as there is no
    hinting available on an empty board.

    But, you can expose most "safe" moves deductively (you can even
    ask it to do that for you with a "trial pick").

    However, you can be left with states where the hints tell you
    N of the remaining N+e squares have mines under them -- yet,
    no way of resolving WHICH is safe and which the likely mine.

    Again, you've invested time very deliberately identifying exactly
    which locations have mines and which are "safe" -- yet are forced
    to GUESS which of the few remaining are mines from ambiguous
    hints.

    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.

    Then every game should be similarly enticing. And, the first
    move shouldn't expose you to a catastrophic failure before
    you've even invested any time.

    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

    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.


    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Waldek Hebisch@3:633/10 to All on Friday, November 20, 2026 19:05:19
    Don Y <blockedofcourse@foo.invalid> wrote:
    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).

    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>
    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)

    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.

    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.

    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.

    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.

    Yes, I was thinking of marking of similar sort.

    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 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.

    --
    Waldek Hebisch

    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Don Y@3:633/10 to All on Friday, November 20, 2026 18:30:15
    On 11/20/2026 12:05 PM, Waldek Hebisch wrote:
    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.

    I just look for patterns -- tracking which digits are
    "possible" (vs. impossible) in each cell and looking at
    the sets of cells (row, column, 3x3 mtarix) to identify
    where a particular digit MUST exist.

    Having made that identification, I revisit the NEW (further
    constrained) possibilities in each cell in that row, column
    and 3x3 matrix.

    Eventually, I get to a solved puzzle *or*, a puzzle where
    none of the remaining undefined cells have "must" contents.
    I.e., now a choice is required. Identifying where the
    BEST choice lies becomes the driving strategy.

    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.

    But, then you have to address backing out when you hit a
    contradiction. That's too much for the effort I want to
    put into such puzzles (I do them "at stoplights" while
    driving; while walking the neighborhood; etc. -- something
    to occupy my mind when my body must be in some particular
    situation).

    I use engineering projects as "difficult puzzles"; these
    (Sudoku, crosswords, etc.) are just small "diversions"...
    things that I can "write off" in a matter of half an hour or less.

    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

    There can be cells with multiple "potential candidates".
    But, making a choice in one of those means you have a
    greater chance of having to back out and try again.

    If, instead, you pick a cell that ONLY has two permissible
    values, then one *may* lead to a solution (though note that
    the (6,8) choices in the aforementioned puzzle don't give
    you any "certain" information (and do not lead to a solution)

    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).

    But, that returns to the original issue: deciding how
    to CREATE puzzles with a specific "degree of difficulty"
    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.

    That tells me nothing about a particular *generated* Sudoku
    (unless I was looking at those generated there)

    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.

    That's /ex post factum/. I'd want to know how to deliberately create
    a puzzle of a particular level of complexity instead of "discovering"
    the complexity of a randomly created puzzle.

    The "game" that I play has decided on different levels of complexity.
    But, offers no clues as to what criteria it uses to make those distinctions.
    It generates a puzzle in constant time so I doubt it is using a hit-or-miss approach.

    If I could dump the ROM, I might reverse engineer the algorithm. But, it
    would be easier to have it available for inspection.

    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.

    But *anything* that an LLM creates is effectively without
    a defining algorithm. Impossible to examine its strategy
    in a way that would let you can that strategy.

    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.



    --- PyGate Linux v1.5.19
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)