• Puzzles

    From Don Y@blockedofcourse@foo.invalid to sci.electronics.design on Mon Nov 9 15:13:37 2026
    From Newsgroup: sci.electronics.design

    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?
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Martin Brown@'''newspam'''@nonad.co.uk to sci.electronics.design on Tue Nov 10 10:02:18 2026
    From Newsgroup: sci.electronics.design

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

    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:-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?

    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

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Don Y@blockedofcourse@foo.invalid to sci.electronics.design on Wed Nov 11 14:31:52 2026
    From Newsgroup: sci.electronics.design

    On 11/10/2026 3:02 AM, Martin Brown wrote:
    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.

    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)
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From antispam@antispam@fricas.org (Waldek Hebisch) to sci.electronics.design on Thu Nov 12 15:15:23 2026
    From Newsgroup: sci.electronics.design

    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
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Don Y@blockedofcourse@foo.invalid to sci.electronics.design on Thu Nov 12 16:11:49 2026
    From Newsgroup: sci.electronics.design

    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]
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From antispam@antispam@fricas.org (Waldek Hebisch) to sci.electronics.design on Sun Nov 15 04:08:11 2026
    From Newsgroup: sci.electronics.design

    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
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Don Y@blockedofcourse@foo.invalid to sci.electronics.design on Sat Nov 14 22:54:56 2026
    From Newsgroup: sci.electronics.design

    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]


    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From antispam@antispam@fricas.org (Waldek Hebisch) to sci.electronics.design on Sun Nov 15 14:13:59 2026
    From Newsgroup: sci.electronics.design

    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
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Johann 'Myrkraverk' Oskarsson@johann@myrkraverk.invalid to sci.electronics.design on Sun Nov 15 22:30:03 2026
    From Newsgroup: sci.electronics.design

    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
    --- Synchronet 3.22a-Linux NewsLink 1.2