From Newsgroup: comp.lang.awk

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

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

On 02.11.2023 17:44, Brian Donnell wrote:

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

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.

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

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

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

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.

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

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

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

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

On Thursday, 2 November 2023 at 11:12:00 UTC-7, Janis Papanagnou wrote:

On 02.11.2023 17:44, Brian Donnell wrote:

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

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.

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

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

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

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.

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

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

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

Mike Sanders <porkchop@invalid.foo> wrote:

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

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

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
On Thursday, 2 November 2023 at 14:06:30 UTC-7, Mike Sanders wrote:

Mike Sanders <pork...@invalid.foo> wrote:

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

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

On 02.11.2023 20:58, Brian Donnell wrote:

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

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

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

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

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
On Thursday, 2 November 2023 at 21:53:08 UTC-7, Janis Papanagnou wrote:

On 02.11.2023 20:58, Brian Donnell wrote:

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

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

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

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

On 03.11.2023 06:09, Brian Donnell wrote:

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.

Good luck with other interesting projects!

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

Have fun!

Janis

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

Brian Donnell <b2donnell@gmail.com> wrote:

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

https://busybox.neocities.org/img/calvin-and-hobbes.png

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

Yes sir, just hop in & go. Its all good.
--
:wq
Mike Sanders

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

On 10/20/2023 6:37 PM, Mike Sanders wrote:

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.

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

Ed Morton <mortonspam@gmail.com> wrote:

Is this:

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

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.

Good info, thanks! Will use this going forward.
--
:wq
Mike Sanders

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

On 06.11.2023 03:29, Mike Sanders wrote:

(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

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

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

On 06.11.2023 03:29, Mike Sanders wrote:

(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

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.
--
:wq
Mike Sanders

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.awk

On 06.11.2023 11:50, Mike Sanders wrote:

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

On 06.11.2023 03:29, Mike Sanders wrote:

(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

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

--- Synchronet 3.20a-Linux NewsLink 1.114