https://busybox.neocities.org/notes/sudoku.txt
https://busybox.neocities.org/notes/sudoku.txt
* 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)
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... ;-)
# ..GNU Awk extensions that would have been useful here...
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: [...]
What codepage should I be using for that encoding? Is it simply UTF8?
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?
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.
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...
[...]
Then swap some columns & rows...
[...]
& 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.
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!
(Oh, my post was not meant as criticism for your approach.)
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.
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 ismgx = "..." is simply a random winning game. But I hasten to add: There
"Yes" I'd just use it.
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
Fisher-Yates...
Sorry for the length of my post. It is a topic that interests me.
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.
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.
So you invented that number? (Or is there a source that I can look up?)
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...
[snip]
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.
[snip links]
But it's a string that was obviously borrowed by a couple sources...
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?)
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.
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?
[...]
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 <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 =)
On 01.11.2023 00:25, Mike Sanders wrote:--- Synchronet 3.20a-Linux NewsLink 1.114
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 multipleNo, it's not bad. It just depends on the intention and context. In
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 =)
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," [...]
On 01.11.2023 05:00, Brian Donnell wrote:--- Synchronet 3.20a-Linux NewsLink 1.114
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
[...]
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
On 02.11.2023 17:44, Brian Donnell wrote:--- Synchronet 3.20a-Linux NewsLink 1.114
[...]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
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?
(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 specialThis is what I called collision classes and if at least a single number
case of this, valid in one row of three blocks. (2's and 5's can also be swapped in these rows.)
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, containsYes, you are right. I missed that combination. (That's why I said that
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.
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(I suppose "%10" should [rather] mean "%9", i.e. modulo 9 ? - Or
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"
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:--This sounds like the approach I implemented, where you did that by incremental construction and I try to prevent zapping the last clue
1. Detect the duals in the intended answer grid and resolve them
with clues in the puzzle grid.
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 constructionSadly I don't understand the question, what you want to express here.
in the fact that a clue connects to 20 other squares and thereby
denies to them the clue's number?
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
Ambiguities...
Mike Sanders <pork...@invalid.foo> wrote:--- Synchronet 3.20a-Linux NewsLink 1.114
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
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 ""
}
}
What is your view on puzzles being symmetrical, or not?
On 02.11.2023 20:58, Brian Donnell wrote:--- Synchronet 3.20a-Linux NewsLink 1.114
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() {Okay, here are the holes. (I used a primitive linear indexing
for (i = 11; i <= 100; i++) {
if (i %10) printf "%d ", grid[i]
else print ""
}
}
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
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!
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.
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.
(elsewhere is was suggested that not all games are winnable &
thats not ture).
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 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.
| Sysop: | DaiTengu |
|---|---|
| Location: | Appleton, WI |
| Users: | 920 |
| Nodes: | 10 (0 / 10) |
| Uptime: | 106:37:34 |
| Calls: | 12,190 |
| Calls today: | 2 |
| Files: | 186,527 |
| Messages: | 2,237,552 |
