Sudoku

[Mike Sanders]

https://busybox.neocities.org/notes/sudoku.txt

usage: awk -f sudoku.txt

example output...

3 4 7 8 9
6 7 8 3 4
1 8 4 3 2 5
7 1 2 9 6 5
4 2 8 1
9 7 1 4
6 7 4 8
3 5 2 9 7
2 8 7 4 6 3

[Janis Papanagnou]

Post by Mike Sanders
https://busybox.neocities.org/notes/sudoku.txt

Nice!

Is there a reference for the design of the algorithm existing?

I'm curious, e.g. about the rationale for the choice of the
mgx = "..." value, for the initial order of the numbers
(before the rows and columns are getting shuffled). Is it a
specific (sort of) "universal" value, or is it one of a couple
existing sequences that have good properties for the task?

Janis

[Janis Papanagnou]

Hi Mike, I'd like to bring the question of this post into mind...

Post by Janis Papanagnou

Post by Mike Sanders
https://busybox.neocities.org/notes/sudoku.txt

Is there a reference for the design of the algorithm existing?
I'm curious, e.g. about the rationale for the choice of the
mgx = "..." value, for the initial order of the numbers
(before the rows and columns are getting shuffled). Is it a
specific (sort of) "universal" value, or is it one of a couple
existing sequences that have good properties for the task?

For the HTML/JS version that I mentioned elsethread I observe
that often there's sheets with ambiguities generated. From some
online resources I've got the impression that you (generally?)
need a Sudoku solver to check the board after generation and if
the test fails then discard the board and retry the generation.

In your Sudoku-script you have used two (arbitrary?) constants
that affect the generation; the initial values in the matrix
before the random shuffle ('mgx') and the number (10) of shuffles.

I'd be interested whether these choices positively affect the
generation generally and the avoidance of ambiguities specifically.
A design reference that can enlighten the issue would also help.

Thanks.

Janis

[Mike Sanders]

Post by Janis Papanagnou

Post by Janis Papanagnou
Is there a reference for the design of the algorithm existing?

Probably several I'm guessing.

Post by Janis Papanagnou

Post by Janis Papanagnou
I'm curious, e.g. about the rationale for the choice of the
mgx = "..." value, for the initial order of the numbers
(before the rows and columns are getting shuffled). Is it a
specific (sort of) "universal" value, or is it one of a couple
existing sequences that have good properties for the task?

Just for fun [*]:

mgx[1] = "123456789456789123789123456214365897365897214897214365531642978642978531978531642"
mgx[2] = "415326789239785416678941235754198623196234857823657194341579862582463971967812345"
mgx[9] = "193724685526819347487653192852491763614237958739568214248975631361142579975386421"
mgx[3] = "123456789456789123789123456214365897365897214897241365532614978641978532978532641"
mgx[4] = "312645978654978123978123654231456789465789231789231465143592867527864391896317542"
mgx[5] = "123456789456789213789321456231468597564297138897135624318654972945712368672943851"
mgx[8] = "315694278628753491479128365132546987764981352985237614243867159857319426961425783"
mgx[6] = "123456789456789123789123456231465897564897231897231564312654978645978312978312645"
mgx[7] = "123456789456789123789123456231465897564897231897312564315648972648972315972531648"

srand()

current_board = mgx[int(rand() * 9) + 1]

Post by Janis Papanagnou
For the HTML/JS version that I mentioned elsethread I observe
that often there's sheets with ambiguities generated. From some
online resources I've got the impression that you (generally?)
need a Sudoku solver to check the board after generation and if
the test fails then discard the board and retry the generation.
In your Sudoku-script you have used two (arbitrary?) constants
that affect the generation; the initial values in the matrix
before the random shuffle ('mgx') and the number (10) of shuffles.
I'd be interested whether these choices positively affect the
generation generally and the avoidance of ambiguities specifically.
A design reference that can enlighten the issue would also help.

Actually, my solution has been called naive, what I'm not so naive about
is p vs. np =)

When we consider the following:

- every game is winnable

- no 1000's of iterations validating *every digit* on a board built
from scratch

- millions (upon millions) of permutations once shuffled & yet millions
more when 'zapped'

Why fuss around getting your work to market when you can instead think
differently? That's my rationale.

Anyhow, (a very, very basic explanation) just start with a winnable
game, a flattened-out string...

123456789578139624496872153952381467641297835387564291719623548864915372235748916

Break it down, step by step...

123456789
578139624496872153952381467641297835387564291719623548864915372235748916

...

Then swap some columns & rows...

+---+
| |
123456789
578139624
496872153 -+
952381467 |
641297835 |
387564291 |
719623548 |
864915372 |
235748916 -+

& randomly zap...

Good luck Janis, I think you have what it takes to get the job done =)

Must go now & more experiments in the days ahead, some boring yet practical,
others more exotic. Its all good.

* For reference, I've 10,000 boards in a zipped plain text file where the
top row is: 123|456|789. There are simply too many possible combinations
to store on my hard-drive. And dont worry about a 'fixed' string, there
are more games possible with a single string than you and I could play
in all our lives combined.

[Janis Papanagnou]

Post by Mike Sanders

Post by Janis Papanagnou

Post by Janis Papanagnou
Is there a reference for the design of the algorithm existing?

Probably several I'm guessing.

Speaking about "solvable" punctured (and guaranteed) solvable code
strings, I haven't found any references. (That's why I'm asking.)

Post by Mike Sanders

Post by Janis Papanagnou

Post by Janis Papanagnou
I'm curious, e.g. about the rationale for the choice of the
mgx = "..." value, for the initial order of the numbers
(before the rows and columns are getting shuffled). Is it a
specific (sort of) "universal" value, or is it one of a couple
existing sequences that have good properties for the task?

mgx[1] = "123456789456789123789123456214365897365897214897214365531642978642978531978531642"
mgx[2] = "415326789239785416678941235754198623196234857823657194341579862582463971967812345"
mgx[9] = "193724685526819347487653192852491763614237958739568214248975631361142579975386421"
mgx[3] = "123456789456789123789123456214365897365897214897241365532614978641978532978532641"
mgx[4] = "312645978654978123978123654231456789465789231789231465143592867527864391896317542"
mgx[5] = "123456789456789213789321456231468597564297138897135624318654972945712368672943851"
mgx[8] = "315694278628753491479128365132546987764981352985237614243867159857319426961425783"
mgx[6] = "123456789456789123789123456231465897564897231897231564312654978645978312978312645"
mgx[7] = "123456789456789123789123456231465897564897231897312564315648972648972315972531648"

Okay. But my previous question whether 'mgx' is defined in a way that
supports producing unambiguous puzzles is now just extended to every
'mgx[i]'; do these mgx[i] have properties to guarantee unambiguous
puzzles?

Post by Mike Sanders
srand()
current_board = mgx[int(rand() * 9) + 1]

Yes, my algorithm is designed to create consistent variants on the fly,
based on the normalized matrix

[
1,2,3, 4,5,6, 7,8,9,
4,5,6, 7,8,9, 1,2,3,
7,8,9, 1,2,3, 4,5,6,

2,3,4, 5,6,7, 8,9,1,
5,6,7, 8,9,1, 2,3,4,
8,9,1, 2,3,4, 5,6,7,

3,4,5, 6,7,8, 9,1,2,
6,7,8, 9,1,2, 3,4,5,
9,1,2, 3,4,5, 6,7,8
];

Then consistent number-mapping and consistent row/column-shuffling
is done. Which at least produces valid solutions. But, with a random
zapping, unambiguous puzzles are not guaranteed here. So the choice
of the initial array is crucial!

Post by Mike Sanders

Post by Janis Papanagnou
For the HTML/JS version that I mentioned elsethread I observe
that often there's sheets with ambiguities generated. From some
online resources I've got the impression that you (generally?)
need a Sudoku solver to check the board after generation and if
the test fails then discard the board and retry the generation.
In your Sudoku-script you have used two (arbitrary?) constants
that affect the generation; the initial values in the matrix
before the random shuffle ('mgx') and the number (10) of shuffles.
I'd be interested whether these choices positively affect the
generation generally and the avoidance of ambiguities specifically.
A design reference that can enlighten the issue would also help.

Actually, my solution has been called naive, what I'm not so naive about
is p vs. np =)

(Oh, my post was not meant as criticism for your approach.)

But maybe this statement implies that 'mgx' does not have any special
properties to prevent ambiguities? - If so, that's okay for me. I was
merely looking for sophisticated _design principles_ - *if* they exist
in the first place.

Post by Mike Sanders
- every game is winnable
- no 1000's of iterations validating *every digit* on a board built
from scratch
- millions (upon millions) of permutations once shuffled & yet millions
more when 'zapped'

(I was not asking for solving NP complete problems.)

Post by Mike Sanders
Why fuss around getting your work to market when you can instead think
differently? That's my rationale.

I'm looking for data sets (or likewise algorithms) that produce
(guaranteed) solvable puzzles.

Post by Mike Sanders
Anyhow, (a very, very basic explanation) just start with a winnable
game, a flattened-out string...

It boils down to: what is a "winnable game [...] string".

Post by Mike Sanders
123456789578139624496872153952381467641297835387564291719623548864915372235748916
Break it down, step by step...
[...]
Then swap some columns & rows...
[...]
& randomly zap...
Good luck Janis, I think you have what it takes to get the job done =)

Well, the random swaps etc. is what I already did from the beginning.
The question is what you mean by
"start with a winnable game, a flattened-out string"

This string that I use is consistent but is this one "winnable"?
123456789456789123789123456234567891567891234891234567345678912678912345912345678
Or a permuted and substituted one derived from that string? I'd say:
No. - Because I could apply simple zaps that produce ambiguities.

If the 'mgx' string is "better"
123456789578139624496872153952381467641297835387564291719623548864915372235748916
I'd like to know why; what are the properties, how are they obtained,
or is it just copied from a source that had only reliable string(s)?
This is the simple but crucial question!

Post by Mike Sanders
Must go now & more experiments in the days ahead, some boring yet practical,
others more exotic. Its all good.
* For reference, I've 10,000 boards in a zipped plain text file where the
top row is: 123|456|789. There are simply too many possible combinations
to store on my hard-drive. And dont worry about a 'fixed' string, there
are more games possible with a single string than you and I could play
in all our lives combined.

I probably wasn't able to make my point clear.

If I'd knew that 'mgx' is a string with good properties (i.e. always
"winnable") then I could just use algebraic permutations on it (as I
already apply them for my initialization string). - If the answer is
"Yes" I'd just use it.

And is one string "better" than others. (And I'm certainly interested
in design principles of these strings. Likewise a database of already
existing strings; no need to duplicate effort.)

Otherwise I'll have to go the path that I found described in several
sources; to create a random board, zap numbers, and test the outcome.
(This test would *not* be a NP complete task.)

Although I tried to comment on each part of your extensive post I
think the answer to the basic question I have can be given simply.

Janis

[Mike Sanders]

Post by Janis Papanagnou
(Oh, my post was not meant as criticism for your approach.)

Its alright Janis =) I meant others, not from this group, characterized
the script as naive, not you (the script is a few yeard old).
In their case, it seems a more sophisticated approach was sought.
I opted instead for simplicity.

Post by Janis Papanagnou
If I'd knew that 'mgx' is a string with good properties (i.e. always
"winnable") then I could just use algebraic permutations on it (as I
already apply them for my initialization string). - If the answer is
"Yes" I'd just use it.

mgx = "..." is simply a random winning game. But I hasten to add: There
are no anomalies that I'm aware of using that particular string of digits
either randomized, or in conjunction with random zapping.

One issue you & I face with these sorts of puzzles (& roman numeral
conversion as well) is, as you've long ago realized: Where do we find
authoritative resources? Me? I don't know...

[Brian Donnell]

Post by Mike Sanders

Post by Janis Papanagnou
(Oh, my post was not meant as criticism for your approach.)

Its alright Janis =) I meant others, not from this group, characterized
the script as naive, not you (the script is a few yeard old).
In their case, it seems a more sophisticated approach was sought.
I opted instead for simplicity.

Post by Janis Papanagnou
If I'd knew that 'mgx' is a string with good properties (i.e. always
"winnable") then I could just use algebraic permutations on it (as I
already apply them for my initialization string). - If the answer is
"Yes" I'd just use it.

mgx = "..." is simply a random winning game. But I hasten to add: There
are no anomalies that I'm aware of using that particular string of digits
either randomized, or in conjunction with random zapping.
One issue you & I face with these sorts of puzzles (& roman numeral
conversion as well) is, as you've long ago realized: Where do we find
authoritative resources? Me? I don't know...
--
:wq
Mike Sanders

Hi, All--
A brute-force, backtracking sudoku solver can generate filled (solved)
grids from empty grids. If a Fisher-Yates shuffle is used to randomize the
order in which the solver attacks the empty grid, any number of random
filled grids can be made. One such grid is:--

146238579
398567421
725914368
283479156
951386247
674125893
862751934
519643782
437892615

If I number the rows 1-9 from top to bottom, and the columns 1-9 from
left to right, I can name each cell uniquely with a 2-digit number, row-
column. So, in the above example, the upper left-hand corner is cell 11,
containing the number 1; the lower right-hand corner is cell 99 = 5; the
center cell is cell 55 = 8; the second cell in the eighth row is 82 = 1.

The filled-in grid has a number of possible ambiguities, e.g., cell 14 = 2,
cell 16 = 8, cell 94 = 8, cell 96 = 2. Cells 14 and 16 can be swapped with
cells 94 and 96 without invalidating the grid. Again, cells 43, 53, 63 can
be swapped with cells 44, 54, 64. (Many other possible ambiguities
exist.) If my purpose be to make a puzzle by subtracting numbers from
the completed grid so as to leave a valid, unambiguous sudoku (no
multiple solutions), then at least one cell of every ambiguity must
become a filled-in, provided clue, yes? I do not know if this "removal"
process is the best approach to making sudoku puzzles.

A program could be written to detect and remove possible ambiguities.
I have not found an easy way to do this, though I suspect one exists.
I do not know if it is possible or desirable to generate solved grids
initially without ambiguities. Removing the ambiguities in the original
filled-in grid by supplying clues does not, of itself, produce a valid
puzzle. Additional clues must be provided to make a single-solution
sudoku.

I suspect that good puzzle generators are proprietary. I do not know
how they insure unique solutions. I do not know if puzzles of a given
difficulty can be produced at will. Perhaps both uniqueness and
difficulty must be established post-generation.

Sorry for the length of my post. It is a topic that interests me.

Best wishes, Brian Donnell

[Mike Sanders]

Brian Donnell <***@gmail.com> wrote:

Good info (many thanks Brain).

Fisher-Yates...

Using Fisher-Yates myself in swap_rows() & swap_columns().

Google also the concepts of 'Bands' and 'Stacks' as it
relates to Sudoku if so compelled, lots of knowledge
in that vain.

Ambiguities... too hard for me to tackle.

[Mike Sanders]

Post by Mike Sanders
Ambiguities...

Just thinking aloud (& not seeking to disturb the flow).

True: random zapping produces ambiguities

True: the numbers needed to solve are always distributed among the ambiguities

True: thus, every game is winnable

[Brian Donnell]

Hi, Mike--Suppose I've solved a grid except for four blank squares which
are the first two squares of the top row and the first two of the bottom
row; and suppose either set of squares can take the numbers 2 and 8--
a dual or ambiguity. If I fill in 28 in the top row, I can fill in 82 in the bottom
row, and vice versa. I would call such a grid "winnable," but I would not
call it "solvable," since no rule or method can resolve the dual except a
coin toss, e.g. In that sense, a completely blank grid, with no clues at all,
is winnable.

IIRC, the Wikipedia Sudoku page suggests that it seems at least 17 clues
are needed for a puzzle to have but a single solution.

Thanks for introducing this topic--I'm having fun.

Brian Donnell

Post by Mike Sanders

Post by Mike Sanders
Ambiguities...

Just thinking aloud (& not seeking to disturb the flow).
True: random zapping produces ambiguities
True: the numbers needed to solve are always distributed among the ambiguities
True: thus, every game is winnable
--
:wq
Mike Sanders

[Mike Sanders]

Post by Brian Donnell
Hi, Mike--Suppose I've solved a grid except for four blank squares which
are the first two squares of the top row and the first two of the bottom
row; and suppose either set of squares can take the numbers 2 and 8--
a dual or ambiguity. If I fill in 28 in the top row, I can fill in 82 in the bottom
row, and vice versa. I would call such a grid "winnable," but I would not
call it "solvable," since no rule or method can resolve the dual except a
coin toss, e.g. In that sense, a completely blank grid, with no clues at all,
is winnable.
IIRC, the Wikipedia Sudoku page suggests that it seems at least 17 clues
are needed for a puzzle to have but a single solution.

Sure enough, a good disticntion between solvable & winnable.

It melts the brain! =)

Loading Image...

Post by Brian Donnell
Thanks for introducing this topic--I'm having fun.

Yes sir, just hop in & go. Its all good.

[Janis Papanagnou]

Post by Brian Donnell
Sorry for the length of my post. It is a topic that interests me.

Not too lengthy. - Very much appreciated. Thanks.

Janis

[Janis Papanagnou]

Post by Mike Sanders

Post by Janis Papanagnou
If I'd knew that 'mgx' is a string with good properties (i.e. always
"winnable") then I could just use algebraic permutations on it (as I
already apply them for my initialization string). - If the answer is
"Yes" I'd just use it.

mgx = "..." is simply a random winning game.

So you invented that number? (Or is there a source that I can look up?)

Post by Mike Sanders
But I hasten to add: There
are no anomalies that I'm aware of using that particular string of digits
either randomized, or in conjunction with random zapping.

Okay. Thanks.

Janis

[Mike Sanders]

Post by Janis Papanagnou
So you invented that number? (Or is there a source that I can look up?)

No, its a selection from among several thousand winning games on file.
The string has a well known & tested pedigree (see links below).
But again, it could've been any other string in the file, if you follow
these rules...

1/5 start with a winning game

2/5 break it down into a grid

3/5 randomly swap rows within the same band (rows not numbers)

4/5 randomly swap columns within the same stack (columns not numbers)

5/5 zap

No one yet has produced an unplayable game from my code. Ambiguities
seem (the idea of multiple solutions), to be non-issue when you start
with a winning game. Or at least, I'm perfectly happy with the resulting
puzzle. Others may disagree, & thats ok =) its all good to me.

https://www.chegg.com/homework-help/questions-and-answers/phyton-verify-solution-valid--sudoku-solution-valid-every-column-row-3x3-square-contains-d-q101818335

https://samgd.com/Sudoku/

https://postgrespro.com/list/thread-id/1492005

https://github.com/norvig/pytudes/blob/main/ipynb/Sudoku%20IPython%20Notebook.ipynb

https://github.com/JanAhrens/sudoku-code-golf/blob/master/README.md

https://www.postgresql.org/message-id/***@mail.gmail.com

https://blogs.fluidinfo.com/fluidinfo/2011/06/15/a-shared-writable-object-for-everything-sudoku-problems/

https://herrickspencer.blog/2011/10/19/the-sudoku-solver-episode-one/

https://www.kaggle.com/code/arturmarkov/cv-lab3

https://csharp.hotexamples.com/examples/Sudoku/Grid/-/php-grid-class-examples.html

[Janis Papanagnou]

Post by Mike Sanders

Post by Janis Papanagnou
So you invented that number? (Or is there a source that I can look up?)

No, its a selection from among several thousand winning games on file.
The string has a well known & tested pedigree (see links below).

Okay, I skimmed through the links and didn't find the qualification
I was seeking (i.e. not one concerning my question at least; okay).

But it's a string that was obviously borrowed by a couple sources;
that answers at least the simple part of my question. Thanks so far!

So I went the other way and just searched that string for ambiguities;
and I found one. The positions marked with 'x' (e.g.) allow two data
entries (7 and 8) for two different possible (ambiguous) solutions
(if these positions get zapped).

zapped original solution A solution B
534 678 912 534 678 912 534 678 912
672 195 348 672 195 348 672 195 348
198 342 567 198 342 567 198 342 567

x59 x61 423 859 761 423 759 861 423
426 x53 x91 426 853 791 426 753 891
x13 924 x56 713 924 856 813 924 756

961 537 284 961 537 284 961 537 284
287 419 635 287 419 635 287 419 635
345 286 179 345 286 179 345 286 179

Post by Mike Sanders
But again, it could've been any other string in the file, if you follow
these rules...

Thanks, but again, this had never been my question! ;-)

(And mind that any possible ambiguities in the original string would
also be found in the consistently transformed strings. - You agree?)

Post by Mike Sanders
[snip]
No one yet has produced an unplayable game from my code.

This obviously proved wrong. (Or am I mistaken with the sample above?)

Post by Mike Sanders
Ambiguities
seem (the idea of multiple solutions), to be non-issue when you start
with a winning game.

After my engagement with that question my _suspicion_ would meanwhile
be that there is no such thing as a "winning game" (an "unambiguous
configuration", as I'd call it). But a suspicion is not a proof, so I
may be wrong. - Maybe I'll work on that question if there's no paper
existing that already answers this question.

Post by Mike Sanders
Or at least, I'm perfectly happy with the resulting
puzzle. Others may disagree, & thats ok =) its all good to me.

Fair enough. :-)

Janis

Post by Mike Sanders
[snip links]

[Mike Sanders]

But it's a string that was obviously borrowed by a couple sources...

Its also the main entry on wikipedia... Most info can be found there
if folks would slowdown & read.

https://en.wikipedia.org/wiki/Sudoku

Ambiguous zapping...

x59 x61 423
426 x53 x91
x13 924 x56

Post by Mike Sanders
No one yet has produced an unplayable game from my code.

This obviously proved wrong. (Or am I mistaken with the sample above?)

For the user, or the grid?

859 761 423
426 853 791
713 924 856

If we're being honest, its the user's perception...

And that's the issue (for some folks), eg, *for some*
ambiguous seems to mean, they'd prefer an easier puzzle.
Hints, clues, safety. Me? I'd ask: Isn't that the fun part
of the game? Otherwise, its asking to bend the rules.

So no, sorry, I remain totally unconvinced by your example.
Evidence of an unsolvable puzzle, not hypotheticals,
is what needs to be produced (along with the seed from
srand() so I can recreate the board).

[Janis Papanagnou]

Post by Mike Sanders

Post by Janis Papanagnou
x59 x61 423
426 x53 x91
x13 924 x56

Post by Mike Sanders
No one yet has produced an unplayable game from my code.

This obviously proved wrong. (Or am I mistaken with the sample above?)

For the user, or the grid?

The created board needs to be consistent; that's quite easy to achieve!
If this is what you mean by "grid" in your question? (I think this is
trivial and IMO not worth a discussion.)

(If you thought that I was just looking for a way how to consistently
arrange the 81 numbers then you gravely misunderstood my posts and also
what I answered on your repeated row/column-permutation digression.)

I've posted a systematic approach in this thread, and you had used one
that looked more random ("unsystematic"). My first impression was that
yours *might* have better properties than my systematic one. Since in
my board I had quickly detected simple zaps that would create ambiguous
challenges. That's why I asked for a design principle (if it exists).

But now that I yet haven't got or found any design principle that will
avoid such non-unambiguously solvable puzzles I closely inspected your
choice; and I found a lot of possible zaps that lead to ambiguities.
Here's my current data based on the 'mgx' string:

Ambiguities in 'mgx' (w:2/8 x:7/8 y:2/5 z:1/6)

534 z7w 9zw
z7w z95 34w
z9w 34w 5z7

xy9 x61 4y3
4y6 xy3 x91
x13 9y4 xy6

961 537 284
287 419 635
345 286 179

If the random zaps will remove the 6 'w' then it's ambiguous! The same
if your zaps will instead remove the 6 'x'. Or the 6 'y'. Or the 6 'z'.

For systematic (valid) permutations of rows and columns, and also for
permutation (remapping) of numbers, this inherent (undesired) property
is persisting. Only that, e.g., all the 'w' are at different positions
in the matrix, or that different numbers than, e.g., 2/8 will produce
that problem.

Post by Mike Sanders
[...]
So no, sorry, I remain totally unconvinced by your example.
Evidence of an unsolvable puzzle, not hypotheticals,
is what needs to be produced (along with the seed from
srand() so I can recreate the board).

What I showed is an evidence that ambiguous solutions happen easily
with the given initialization strings. The ambiguity will not show up
if not all the 'w' (or not all the 'x', etc.) will be zapped. But if
the RNG hit all the 'w' ('x', etc.) it's ambiguous, and the more zaps
you choose the more likely it is that you will get ambiguous solutions.

This isn't important if Sudoku software only checks the validity of a
solution (once at the end). Several Sudoku software I played did not
check the validity (once or anew) but compared the solution with the
initial (unzapped) configuration; and this makes sense since Sudoku
software provides features to show or reject "errors" during play,[*]
and for that it is important for the software to have an unambiguous
configuration - it must be able to know whether at a specific zapped
place requires a 2 or a 8 to insert.

I was "merely" looking for a design that minimizes such ambiguities.
(If one exists in the first place.)

So I think I explained everything necessary, and I will abstain now.

Have fun!

Janis

[*] If one's software doesn't support such a feature you maybe don't
need unambiguity, but the interactive test algorithm of the software
must then be much more permissive and more sophisticated.

[Mike Sanders]

Post by Janis Papanagnou
After my engagement with that question my _suspicion_ would meanwhile
be that there is no such thing as a "winning game" (an "unambiguous
configuration", as I'd call it). But a suspicion is not a proof, so I
may be wrong. - Maybe I'll work on that question if there's no paper
existing that already answers this question.

(Forgot to add) I guess, folks want a single solvable game per board.
I'm not sure that's always going to be the case, as your example pointed
out earlier. I'm thinking lots of code does this too, but who knows?
Maybe you or others can cobble together a work around. But why? If multiple
solutions are possible, I, speaking only for myself, don't feel its such
a bad thing. Maybe its just my way of thinking (my bias =)

[Janis Papanagnou]

Post by Mike Sanders

Post by Janis Papanagnou
After my engagement with that question my _suspicion_ would meanwhile
be that there is no such thing as a "winning game" (an "unambiguous
configuration", as I'd call it). But a suspicion is not a proof, so I
may be wrong. - Maybe I'll work on that question if there's no paper
existing that already answers this question.

(Forgot to add) I guess, folks want a single solvable game per board.
I'm not sure that's always going to be the case, as your example pointed
out earlier. I'm thinking lots of code does this too, but who knows?
Maybe you or others can cobble together a work around. But why? If multiple
solutions are possible, I, speaking only for myself, don't feel its such
a bad thing. Maybe its just my way of thinking (my bias =)

No, it's not bad. It just depends on the intention and context. In
my other recent post I already explained the rationale for why I'm
looking for good initial "configurations". It's for contexts where
the implemented game wants to notify the player about errors; for
that (e.g.) it is important to know what the expected solution is.
If, OTOH, all you want is to wait until the game has been played
to end, then you need just one consistency check at the end, and
it's unimportant in that case whether you permuted the '2' and '8'
(if it's otherwise still consistent).

Okay, enough for now. :-)

Janis

[Brian Donnell]

Hi, All--
Thanks, Janis! You've shown me a new kind of ambiguity that I had
not known.

I'm going to rename "ambiguities," and call them "duals," after the
usage of chess players when discussing chess problems that have
more than one solution. Duals are not a problem in the solution--
they are a problem in the puzzle that intends that solution. Duals
are a flaw in chess problems and they are a flaw in sudoku puzzles
for at least two reasons:--

1. If duals are allowed, I can make sudoku puzzles by removing willy-
nilly as many numbers as I like from a finished, valid, solved grid,
from 1 to 81. If I remove only one, leaving 80 as "clues," the "solution"
is unique and trivial; if I remove four that are a dual, two solutions are
possible; if I remove all 81, all valid sudoku solutions are possible.

2. Sudoku is an NP-complete problem. Algorithmic solvers have been
built, as well as brute-force solvers. Such solvers use algorithms for
Hidden and Naked Singles, Doubles, Triples, and Quads; Pointing and
Claiming; X-Wings and XY-Wings; Jellyfish, Swordfish, and Death
Blossoms(!). I'm thinking that the more solutions a sudoku puzzle
has, the fewer and less-advanced are the algorithmic techniques
needed to solve it, if they can be used at all. Pity if the ingenious
algorithms be deprecated: a blank grid cannot be solved using
them.

Brian Donnell

Post by Janis Papanagnou

Post by Mike Sanders

Post by Janis Papanagnou
After my engagement with that question my _suspicion_ would meanwhile
be that there is no such thing as a "winning game" (an "unambiguous
configuration", as I'd call it). But a suspicion is not a proof, so I
may be wrong. - Maybe I'll work on that question if there's no paper
existing that already answers this question.

(Forgot to add) I guess, folks want a single solvable game per board.
I'm not sure that's always going to be the case, as your example pointed
out earlier. I'm thinking lots of code does this too, but who knows?
Maybe you or others can cobble together a work around. But why? If multiple
solutions are possible, I, speaking only for myself, don't feel its such
a bad thing. Maybe its just my way of thinking (my bias =)

No, it's not bad. It just depends on the intention and context. In
my other recent post I already explained the rationale for why I'm
looking for good initial "configurations". It's for contexts where
the implemented game wants to notify the player about errors; for
that (e.g.) it is important to know what the expected solution is.
If, OTOH, all you want is to wait until the game has been played
to end, then you need just one consistency check at the end, and
it's unimportant in that case whether you permuted the '2' and '8'
(if it's otherwise still consistent).
Okay, enough for now. :-)
Janis

[Janis Papanagnou]

Post by Brian Donnell
Hi, All--
Thanks, Janis! You've shown me a new kind of ambiguity that I had
not known.
I'm going to rename "ambiguities," and call them "duals," [...]

For the problem per se and a naming alternative in Sudoku contexts
see also [1].

BTW, I've implemented a simple counter measure for the issue in my
Javascript version. It's not perfect but the simple ambiguities I
showed upthread are handled nicely; I've manually identified these
collision classes for the fixed initialization string, and before
zapping numbers from that string I check whether there's still one
number in every identified class remaining (which I then don't zap).
More complex patterns I cannot detect, though, - it would require
a more thorough (or an algorithmic) analysis of the initialization
string. A sample of a yet unhandled more complex collision pattern
can be seen at [2], where the six orange numbers 5 and 8 can also
be consistently swapped to create a valid solution.

Janis

[1] https://www.sudokuwiki.org/Avoidable_Rectangles

[2] Loading Image...

[Brian Donnell]

Thanks for the links, Janis. I'll try to understand them with a little study.
Meanwhile, I've come to the conclusion that a finished, correct sudoku
grid (a solved grid) is nothing but ambiguities. In any completed grid,
any two digits, say 7 and 8, can be swapped throughout the grid with-
out making the grid invalid, yes?

This means that at least 8 of the 9 digits must be used in the puzzle as
clues to avoid duals. Your example above, of 7's and 8's is a special
case of this, valid in one row of three blocks. (2's and 5's can also be
swapped in these rows.) The middle example, Solution A, contains
other duals: e.g., the first three numbers of the top row, 534, can be
swapped with the first three numbers of the bottom row, 345.

Also, every row and column of three blocks must contain a clue, or
the single rows or columns within can be swapped.

I've used "my" method of numbering cells (with 2 numbers instead of
a letter and a number) in several programs, and am loath to change.
It simplifies certain searches: by reversing the row-column numbers
to column-row, one can walk rows or columns. Again, one can popu-
late an array by advancing a counter in a "for" loop; and by using "%10"
one can avoid out-of-grid squares in a "PrintGrid()" function.

I've been able to make an easy-to-medium puzzle by iteration:--
1. Detect the duals in the intended answer grid and resolve them
with clues in the puzzle grid.
2. Solve the puzzle grid. If this solution does not match the intended
solution, resolve the new duals.
3. Repeat until puzzle grid solution matches intended solution.

Unfortunately, all the "detection," as well as the final evaluation of
difficulty I had to do by hand...

I had a thought last night: is there anything useful to construction
in the fact that a clue connects to 20 other squares and thereby
denies to them the clue's number?

Brian Donnell

Post by Janis Papanagnou

Post by Brian Donnell
Hi, All--
Thanks, Janis! You've shown me a new kind of ambiguity that I had
not known.
I'm going to rename "ambiguities," and call them "duals," [...]

For the problem per se and a naming alternative in Sudoku contexts
see also [1].
BTW, I've implemented a simple counter measure for the issue in my
Javascript version. It's not perfect but the simple ambiguities I
showed upthread are handled nicely; I've manually identified these
collision classes for the fixed initialization string, and before
zapping numbers from that string I check whether there's still one
number in every identified class remaining (which I then don't zap).
More complex patterns I cannot detect, though, - it would require
a more thorough (or an algorithmic) analysis of the initialization
string. A sample of a yet unhandled more complex collision pattern
can be seen at [2], where the six orange numbers 5 and 8 can also
be consistently swapped to create a valid solution.
Janis
[1] https://www.sudokuwiki.org/Avoidable_Rectangles
[2] http://volatile.gridbug.de/ambiguity_v1_nr1.png

[Janis Papanagnou]

Post by Brian Donnell
[...]
Meanwhile, I've come to the conclusion that a finished, correct sudoku
grid (a solved grid) is nothing but ambiguities. In any completed grid,
any two digits, say 7 and 8, can be swapped throughout the grid with-
out making the grid invalid, yes?

Don't mix two issues. - You can always (consistently!) substitute two
numbers of any sheet. This is what I've meanwhile done in two contexts
(in Sudoku and in a Mastermind solver); intention is to mimic variety
(without actually changing complexity or making things unsolvable).
And the other issue is the one we've been discussing, symmetries in
conjunction with more or less difficult solutions by "zapping" (that
affects unique solvability); I partly addressed that in my current JS
implementation.

Post by Brian Donnell
This means that at least 8 of the 9 digits must be used in the puzzle as
clues to avoid duals.

Actually I sometimes had games where a number was completely absent in
the beginning and only one instance of a second number was existing.
The solvability is not directly affected by such a configuration; you
may or may not solve such games purely and deterministically "by logic",
since solvability obviously depends on other factors (zapping grade and
actual layout). Thus far my observations.

Post by Brian Donnell
Your example above, of 7's and 8's is a special
case of this, valid in one row of three blocks. (2's and 5's can also be
swapped in these rows.)

This is what I called collision classes and if at least a single number
from such a set is not zapped can basically be solved (unless there are
other layout or combination problems existing.)

Post by Brian Donnell
The middle example, Solution A, contains
other duals: e.g., the first three numbers of the top row, 534, can be
swapped with the first three numbers of the bottom row, 345.

Yes, you are right. I missed that combination. (That's why I said that
a more thorough analysis of an initial configuration string would be
necessary.) Since my posting where you saw "Solution A" I meanwhile
also found more sets and added them to my script. My current matrix is

0,0,0, 1,0,2, 0,1,2,
1,0,2, 1,0,0, 0,0,2,
1,0,2, 0,0,2, 0,1,0,

3,4,0, 3,0,5, 0,4,5,
0,4,0, 3,4,5, 3,0,5,
3,0,0, 0,4,0, 3,4,0,

0,0,0, 6,0,0, 0,0,6,
0,0,0, 6,0,0, 0,0,6,
0,0,0, 0,0,0, 0,0,0

where equal numbers are of the same "ambiguity set". (And you see the
positions for 534 and 345 are still 0,0,0 - i.e. are not considered.)

Post by Brian Donnell
Also, every row and column of three blocks must contain a clue, or
the single rows or columns within can be swapped.
I've used "my" method of numbering cells (with 2 numbers instead of
a letter and a number) in several programs, and am loath to change.
It simplifies certain searches: by reversing the row-column numbers
to column-row, one can walk rows or columns. Again, one can popu-
late an array by advancing a counter in a "for" loop; and by using "%10"

(I suppose "%10" should [rather] mean "%9", i.e. modulo 9 ? - Or
otherwise you'd need holes in the iterated data to be ignored.)

Post by Brian Donnell
one can avoid out-of-grid squares in a "PrintGrid()" function.
I've been able to make an easy-to-medium puzzle by iteration:--
1. Detect the duals in the intended answer grid and resolve them
with clues in the puzzle grid.

This sounds like the approach I implemented, where you did that by
incremental construction and I try to prevent zapping the last clue
number.

Post by Brian Donnell
2. Solve the puzzle grid. If this solution does not match the intended
solution, resolve the new duals.
3. Repeat until puzzle grid solution matches intended solution.
Unfortunately, all the "detection," as well as the final evaluation of
difficulty I had to do by hand...
I had a thought last night: is there anything useful to construction
in the fact that a clue connects to 20 other squares and thereby
denies to them the clue's number?

Sadly I don't understand the question, what you want to express here.

Janis

Post by Brian Donnell
Brian Donnell

Post by Janis Papanagnou

Post by Brian Donnell
Hi, All--
Thanks, Janis! You've shown me a new kind of ambiguity that I had
not known.
I'm going to rename "ambiguities," and call them "duals," [...]

For the problem per se and a naming alternative in Sudoku contexts
see also [1].
BTW, I've implemented a simple counter measure for the issue in my
Javascript version. It's not perfect but the simple ambiguities I
showed upthread are handled nicely; I've manually identified these
collision classes for the fixed initialization string, and before
zapping numbers from that string I check whether there's still one
number in every identified class remaining (which I then don't zap).
More complex patterns I cannot detect, though, - it would require
a more thorough (or an algorithmic) analysis of the initialization
string. A sample of a yet unhandled more complex collision pattern
can be seen at [2], where the six orange numbers 5 and 8 can also
be consistently swapped to create a valid solution.
Janis
[1] https://www.sudokuwiki.org/Avoidable_Rectangles
[2] http://volatile.gridbug.de/ambiguity_v1_nr1.png

[Brian Donnell]

Hi, Janis--Can you tell I'm a retired AWK hobbyist with time on my hands?

I agree in the main with your remarks. As to "%10":--

function PrintGrid() {
for (i = 11; i <= 100; i++) {
if (i %10) printf "%d ", grid[i]
else print ""
}
}

As to my vague closing thought, I was wondering if the "removal"
approach to making puzzles may not be the easiest. What if I
started with an empty grid, in which each cell has all 9 digits for
candidates? If I place a clue, it eliminates that number from the
candidate list of 20 other connected cells. Can I continue to place
clues until...something...happens? (I wish I'd paid more attention
during that Discrete Mathematics class.) A bitmap (?) is useful:--

grid[sq] = 000010000 # sq contains "5," or has room only for 5.
grid[sq] = 111111111 # all 9 numbers are candidates in sq.
grid[sq[ = 111101111 # 5 is not a candidate in sq.

I think you can ignore this idle thought of mine.

What is your view on puzzles being symmetrical, or not?

Brian Donnell

Post by Janis Papanagnou

Post by Brian Donnell
[...]
Meanwhile, I've come to the conclusion that a finished, correct sudoku
grid (a solved grid) is nothing but ambiguities. In any completed grid,
any two digits, say 7 and 8, can be swapped throughout the grid with-
out making the grid invalid, yes?

Don't mix two issues. - You can always (consistently!) substitute two
numbers of any sheet. This is what I've meanwhile done in two contexts
(in Sudoku and in a Mastermind solver); intention is to mimic variety
(without actually changing complexity or making things unsolvable).
And the other issue is the one we've been discussing, symmetries in
conjunction with more or less difficult solutions by "zapping" (that
affects unique solvability); I partly addressed that in my current JS
implementation.

Post by Brian Donnell
This means that at least 8 of the 9 digits must be used in the puzzle as
clues to avoid duals.

Actually I sometimes had games where a number was completely absent in
the beginning and only one instance of a second number was existing.
The solvability is not directly affected by such a configuration; you
may or may not solve such games purely and deterministically "by logic",
since solvability obviously depends on other factors (zapping grade and
actual layout). Thus far my observations.

Post by Brian Donnell
Your example above, of 7's and 8's is a special
case of this, valid in one row of three blocks. (2's and 5's can also be
swapped in these rows.)

This is what I called collision classes and if at least a single number
from such a set is not zapped can basically be solved (unless there are
other layout or combination problems existing.)

Post by Brian Donnell
The middle example, Solution A, contains
other duals: e.g., the first three numbers of the top row, 534, can be
swapped with the first three numbers of the bottom row, 345.

Yes, you are right. I missed that combination. (That's why I said that
a more thorough analysis of an initial configuration string would be
necessary.) Since my posting where you saw "Solution A" I meanwhile
also found more sets and added them to my script. My current matrix is
0,0,0, 1,0,2, 0,1,2,
1,0,2, 1,0,0, 0,0,2,
1,0,2, 0,0,2, 0,1,0,
3,4,0, 3,0,5, 0,4,5,
0,4,0, 3,4,5, 3,0,5,
3,0,0, 0,4,0, 3,4,0,
0,0,0, 6,0,0, 0,0,6,
0,0,0, 6,0,0, 0,0,6,
0,0,0, 0,0,0, 0,0,0
where equal numbers are of the same "ambiguity set". (And you see the
positions for 534 and 345 are still 0,0,0 - i.e. are not considered.)

Post by Brian Donnell
Also, every row and column of three blocks must contain a clue, or
the single rows or columns within can be swapped.
I've used "my" method of numbering cells (with 2 numbers instead of
a letter and a number) in several programs, and am loath to change.
It simplifies certain searches: by reversing the row-column numbers
to column-row, one can walk rows or columns. Again, one can popu-
late an array by advancing a counter in a "for" loop; and by using "%10"

(I suppose "%10" should [rather] mean "%9", i.e. modulo 9 ? - Or
otherwise you'd need holes in the iterated data to be ignored.)

Post by Brian Donnell
one can avoid out-of-grid squares in a "PrintGrid()" function.
I've been able to make an easy-to-medium puzzle by iteration:--
1. Detect the duals in the intended answer grid and resolve them
with clues in the puzzle grid.

This sounds like the approach I implemented, where you did that by
incremental construction and I try to prevent zapping the last clue
number.

Post by Brian Donnell
2. Solve the puzzle grid. If this solution does not match the intended
solution, resolve the new duals.
3. Repeat until puzzle grid solution matches intended solution.
Unfortunately, all the "detection," as well as the final evaluation of
difficulty I had to do by hand...
I had a thought last night: is there anything useful to construction
in the fact that a clue connects to 20 other squares and thereby
denies to them the clue's number?

Sadly I don't understand the question, what you want to express here.
Janis

Post by Brian Donnell
Brian Donnell

Post by Janis Papanagnou

Post by Brian Donnell
Hi, All--
Thanks, Janis! You've shown me a new kind of ambiguity that I had
not known.
I'm going to rename "ambiguities," and call them "duals," [...]

For the problem per se and a naming alternative in Sudoku contexts
see also [1].
BTW, I've implemented a simple counter measure for the issue in my
Javascript version. It's not perfect but the simple ambiguities I
showed upthread are handled nicely; I've manually identified these
collision classes for the fixed initialization string, and before
zapping numbers from that string I check whether there's still one
number in every identified class remaining (which I then don't zap).
More complex patterns I cannot detect, though, - it would require
a more thorough (or an algorithmic) analysis of the initialization
string. A sample of a yet unhandled more complex collision pattern
can be seen at [2], where the six orange numbers 5 and 8 can also
be consistently swapped to create a valid solution.
Janis
[1] https://www.sudokuwiki.org/Avoidable_Rectangles
[2] http://volatile.gridbug.de/ambiguity_v1_nr1.png

[Janis Papanagnou]

Post by Brian Donnell
Can you tell I'm a retired AWK hobbyist with time on my hands?

After we immerged a bit into the theory of Sudoku we should not
forget that we're in an Awk newsgroup. :-)

Post by Brian Donnell
I agree in the main with your remarks. As to "%10":--
function PrintGrid() {
for (i = 11; i <= 100; i++) {
if (i %10) printf "%d ", grid[i]
else print ""
}
}

Okay, here are the holes. (I used a primitive linear indexing
0..80 and thus calculated div and mod 9 to get row and columns.)

Post by Brian Donnell
What is your view on puzzles being symmetrical, or not?

Sadly, again I don't know what you're referring here. - You mean
symmetrical Sudokus (what would that be?), or other puzzles now?

I think I've done enough Sudoku (theory and implementation) for
the moment. (Now turning to something "completely different" ;-)

Janis

[Brian Donnell]

Hi, Janis--By symmetry, I mean that the clues in the puzzle are
arranged in point-symmetry about the center square. Most of the
puzzles I see in various periodicals are such, though there is no
reason they need be.

Good luck with other interesting projects!

Brian Donnell

Post by Janis Papanagnou

Post by Brian Donnell
Can you tell I'm a retired AWK hobbyist with time on my hands?

After we immerged a bit into the theory of Sudoku we should not
forget that we're in an Awk newsgroup. :-)

Post by Brian Donnell
I agree in the main with your remarks. As to "%10":--
function PrintGrid() {
for (i = 11; i <= 100; i++) {
if (i %10) printf "%d ", grid[i]
else print ""
}
}

Okay, here are the holes. (I used a primitive linear indexing
0..80 and thus calculated div and mod 9 to get row and columns.)

Post by Brian Donnell
What is your view on puzzles being symmetrical, or not?

Sadly, again I don't know what you're referring here. - You mean
symmetrical Sudokus (what would that be?), or other puzzles now?
I think I've done enough Sudoku (theory and implementation) for
the moment. (Now turning to something "completely different" ;-)
Janis

[Janis Papanagnou]

Post by Brian Donnell
Hi, Janis--By symmetry, I mean that the clues in the puzzle are
arranged in point-symmetry about the center square. Most of the
puzzles I see in various periodicals are such, though there is no
reason they need be.

Ah, okay. I'm not that deep into the topic to have noticed. ;-)
I'm more interested in the algorithms, not so much in eye candy.

Post by Brian Donnell
Good luck with other interesting projects!

It's basically just mundane Real Life projects I have in mind.

Have fun!

Janis

[Kaz Kylheku]

Post by Mike Sanders
Then swap some columns & rows...
+---+
| |
123456789
578139624
496872153 -+
952381467 |
641297835 |
387564291 |
719623548 |
864915372 |
235748916 -+

I don't believe you can swap those columsn and rows!

Because look, in the case of the two rows, you're taking the upper right
square:

789
624
153

and replacing the bottom 153 with 916, which is invalid; you end up
with two 6s and two 9s in that square.

I think, you can only exchange colums and rows within the same group of 3,
so that you don't change the contents of any 3x3 square.

Also, I think you can exchange groups of 3 rows that contain whole 3x3
squares. I.e. if we regard the whole sudoku board to be

A B C

D E F

G H I

where the letters represent 3x3 squares, we can swap A B C with D E F,
and so on, and likewise in the columns. (We couldn't do that if the
A-E-I diagonal mattered, but it doesn't.)

[Mike Sanders]

Kaz Kylheku <864-117-***@kylheku.com> wrote:

Well, long time since we've spoken Kaz. Hope
you're doing alright.

Post by Kaz Kylheku
I don't believe you can swap those columsn and rows!

That was only a textual diagram to illustrate concept.
Please run the script instead.

[Janis Papanagnou]

Hi Mike

Post by Mike Sanders
https://busybox.neocities.org/notes/sudoku.txt

Based on your code I make some changes and additions
that you find at: http://random.gridbug.de/sudoku.awk
(This code is not yet cleaned up to make it easier for
you to spot the changes in case you're interested to
adopt some of them.)

* output indexes (x,y) in your print routine have been
swapped (to reflect mathematical naming conventions)
* difficulty function introduced that is fed by a
program argument (1..5, and a default)
* randomly permuted the numbers from the 'mgx' values
(not sure whether it functionally adds anything to
randomness - see my question about 'mgx' in my other
post - but if so, it's here to use at least)
* added a (Unicode characters) frame to the raw numbers
output so that output looks better (depending on the
used terminal); currently both layouts are printed

Next step would be to support solving the Sudoku
interactively... ;-)

Janis

[Janis Papanagnou]

Post by Janis Papanagnou
* randomly permuted the numbers from the 'mgx' values
(not sure whether it functionally adds anything to
randomness - see my question about 'mgx' in my other
post - but if so, it's here to use at least)

It just occurred to me that this formulation is misleading.

Not the numbers in the 'mgx' array are permuted but the
_digits_ 1..9 are _consistently_ permuted. So instead of
using (informally written) mgx[i] we use map[mgx[i]] .

Janis

[Mike Sanders]

Post by Janis Papanagnou
Hi Mike

Post by Mike Sanders
https://busybox.neocities.org/notes/sudoku.txt

Based on your code I make some changes and additions
that you find at: http://random.gridbug.de/sudoku.awk
(This code is not yet cleaned up to make it easier for
you to spot the changes in case you're interested to
adopt some of them.)
* output indexes (x,y) in your print routine have been
swapped (to reflect mathematical naming conventions)
* difficulty function introduced that is fed by a
program argument (1..5, and a default)
* randomly permuted the numbers from the 'mgx' values
(not sure whether it functionally adds anything to
randomness - see my question about 'mgx' in my other
post - but if so, it's here to use at least)
* added a (Unicode characters) frame to the raw numbers
output so that output looks better (depending on the
used terminal); currently both layouts are printed
Next step would be to support solving the Sudoku
interactively... ;-)

Hey Janis =)

Your take looks wonderful! I can only reply quickly because
I have company visiting for a week or so & I must be a good
host, but nevertheless...

Post by Janis Papanagnou
# ..GNU Awk extensions that would have been useful here...

Yes you *should* rewrite for Gawk, in fact I hope you will.
See where it takes us. Why not? This is exactly why (I know,
I know I've said it before) you need to share your code & notes.

Under Windows I seem to be having trouble with the character
encoding you're using. Screen shot here:

https://drive.google.com/file/d/1HomdPt67LGbLOZnuKumDx0iiAbldAN5V/view

What codepage should I be using for that encoding? Is it simply UTF8?

Still, realy (really!) great stuff I'm so glad you extended the script
(& you should place your name more clearly in the script so easier to see,
dont be shy).

Must go, will post lots more interesting, atypical stuff in the coming
weeks for us all to chew on, or at least make fun of =) And you should
post your ideas/code too, have fun I say. It better to learn, no?

Mucho thanks Janis.

[Janis Papanagnou]

Post by Mike Sanders

Post by Janis Papanagnou
* added a (Unicode characters) frame to the raw numbers
output so that output looks better (depending on the
used terminal); currently both layouts are printed

Under Windows I seem to be having trouble with the character
encoding you're using. Screen shot here: [...]

Oh, yes, I feared that. :-}

With my settings the terminal output for a ("difficulty level" 3)
Sudoku board looks like this: Loading Image...
(I currently print both, the raw text and the framed one, to better
see the difference and spot any errors I may have made.)

Post by Mike Sanders
What codepage should I be using for that encoding? Is it simply UTF8?

Character encodings can be a pain and if third party systems are
involved I can hardly help. All I can say is that I switched to
Unicode a long time ago, and my character encoding is generally
UTF-8. This is the most flexible and contemporary quasi-standard
setting, in my book.

On Windows, I recall, there's some "extended ASCII" standard that
has its own set of "boxing characters". So you could transcribe
the UTF-8/Unicode characters to that code set. But I'd rather try
to configure my system with UTF-8 Unicode encoding, if possible.

WRT transcribing Sudoku to GNU Awk; that must wait! Currently I'm
writing a Javascript version. ;-) I like playing Sudoku, and the
web versions I saw thus far didn't fit my taste. So your post was
the trigger to write my own HTML/JS version.

Janis

[Ed Morton]

Post by Mike Sanders
https://busybox.neocities.org/notes/sudoku.txt

Is this:

seed = srand(123456789)

which will make every run of the script use the same "random" numbers
deliberate and, if so, why?

Regarding:

GRID[row, col]

don't use all upper case for user-defined variables so they can't clash
with any awk builtin variables of which there are many more than I'd
care to try to list, they vary by awk variant (GNU, BSD, busybox, etc.),
and others could be introduced in future.

Ed.

[Mike Sanders]

Post by Ed Morton
seed = srand(123456789)
which will make every run of the script use the same "random" numbers
deliberate and, if so, why?

Yes. A temperary & now removed measure to pruduce the same seed
(elsewhere is was suggested that not all games are winnable &
thats not ture).

Script rolled back/reverted...

Post by Ed Morton
GRID[row, col]
don't use all upper case for user-defined variables so they can't clash
with any awk builtin variables of which there are many more than I'd
care to try to list, they vary by awk variant (GNU, BSD, busybox, etc.),
and others could be introduced in future.

Good info, thanks! Will use this going forward.

[Janis Papanagnou]

Post by Mike Sanders
(elsewhere is was suggested that not all games are winnable &
thats not ture).

You said that before, but I cannot see where that was claimed.

In case that you permute a _consistent_ string of numbers...
(a) you can also find (one or more!) consistent solutions,
(b) in case of _more than one_ possible solution there's an
ambiguity that obviously cannot be resolved.
The probability for ambiguities to appear is depending
on the number of zaps; I had posted an example for that.

Janis

[Mike Sanders]

Post by Janis Papanagnou

Post by Mike Sanders
(elsewhere is was suggested that not all games are winnable &
thats not ture).

You said that before, but I cannot see where that was claimed.

Elsewhere != here

Post by Janis Papanagnou
In case that you permute a _consistent_ string of numbers...
(a) you can also find (one or more!) consistent solutions,
(b) in case of _more than one_ possible solution there's an
ambiguity that obviously cannot be resolved.
The probability for ambiguities to appear is depending
on the number of zaps; I had posted an example for that.

We'll simply have to agree to disagree on the meaning of winnable.
Sometimes life is like that Janis.

[Janis Papanagnou]

Post by Mike Sanders

Post by Janis Papanagnou

Post by Mike Sanders
(elsewhere is was suggested that not all games are winnable &
thats not ture).

You said that before, but I cannot see where that was claimed.

Elsewhere != here

Post by Janis Papanagnou
In case that you permute a _consistent_ string of numbers...
(a) you can also find (one or more!) consistent solutions,
(b) in case of _more than one_ possible solution there's an
ambiguity that obviously cannot be resolved.
The probability for ambiguities to appear is depending
on the number of zaps; I had posted an example for that.

We'll simply have to agree to disagree on the meaning of winnable.

I generally spoke about unique (unambiguous) solutions, not
about the term "winnable" (which needs a definition), so we
cannot disagree (since we have probably been speaking about
different things). - My suspicion is that by "winnable" you
mean he case (a); which is perfectly fine for me.

Janis