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

--
:wq
Mike Sanders

On 21.10.2023 01:37, Mike Sanders wrote:
> 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

Hi Mike

On 21.10.2023 01:37, Mike Sanders wrote:
> 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

On 21.10.2023 15:16, Janis Papanagnou wrote:
> * 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

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

> Hi Mike
>
> On 21.10.2023 01:37, Mike Sanders wrote:
>> 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...

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

--
:wq
Mike Sanders

On 21.10.2023 23:12, Mike Sanders wrote:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>> * 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: http://volatile.gridbug.de/mike.png
(I currently print both, the raw text and the framed one, to better
see the difference and spot any errors I may have made.)

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

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

On 21.10.2023 04:24, Janis Papanagnou wrote:
> On 21.10.2023 01:37, Mike Sanders wrote:
>> 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

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

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

Probably several I'm guessing.
>> 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]

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

--
:wq
Mike Sanders

On 29.10.2023 04:57, Mike Sanders wrote:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>
>>> 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.)

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

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?

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

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

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

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

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

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

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

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

On 2023-10-29, Mike Sanders <porkchop@invalid.foo> wrote:
> 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.)

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

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

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

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

--
:wq
Mike Sanders

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

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

On Sunday, 29 October 2023 at 12:16:13 UTC-7, Mike Sanders wrote:
> Janis Papanagnou <janis_pap...@hotmail.com> wrote:
>
> > (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.
> > 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

Brian Donnell <b2donnell@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.

--
:wq
Mike Sanders

On 30.10.2023 21:18, Brian Donnell wrote:
>
> Sorry for the length of my post. It is a topic that interests me.

Not too lengthy. - Very much appreciated. Thanks.

Janis

On 29.10.2023 20:16, Mike Sanders wrote:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>
>> 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?)

> 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

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

> 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/e08cc0400911042333o5361b21cu2c9438f82b1e55ce@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

--
:wq
Mike Sanders

On 31.10.2023 20:18, Mike Sanders wrote:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>
>> 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

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

> [snip]
>
> No one yet has produced an unplayable game from my code.

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

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

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

Fair enough. :-)

Janis

> [snip links]

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

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

--
:wq
Mike Sanders

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

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

--
:wq
Mike Sanders

On 31.10.2023 22:59, Mike Sanders wrote:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>
>> x59 x61 423
>> 426 x53 x91
>> x13 924 x56
>>
>>> 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.

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

On 01.11.2023 00:25, Mike Sanders wrote:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>
>> 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

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

On Tuesday, 31 October 2023 at 16:54:18 UTC-7, Janis Papanagnou wrote:
> On 01.11.2023 00:25, Mike Sanders wrote:
> > Janis Papanagnou <janis_pap...@hotmail.com> wrote:
> >
> >> 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

On 01.11.2023 05:00, Brian Donnell wrote:
> 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

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

On Wednesday, 1 November 2023 at 21:10:09 UTC-7, Janis Papanagnou wrote:
> On 01.11.2023 05:00, Brian Donnell wrote:
> > 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