The New Sudoku Players' Forum

[Papy]

In this version of the Solveur you well have 25 grids original and I make morphs
It' funny because they are not what you find

Code: Select all

  Tb[1] := '_______1_4_________2___________5_4_7__8___3____1_9____3__4__2___5_1________8_6___';
  Tb[2] := '693784512487512936125963874932651487568247391741398625319475268856129743274836159';
  Tb[3] := '_______1_4_________2___________5_6_4__8___3____1_9____3__4__2___5_1________8_7___';
  Tb[4] := '793684512486512937125973846932751684578246391641398725319465278857129463264837159';
  Tb[5] := '_______12____35______6___7_7_____3_____4__8__1___________12_____8_____4__5____6__';
  Tb[6] := '673894512912735486845612973798261354526473891134589267469128735287356149351947628';
  Tb[7] := '_______12__36__________7___41__2_______5__3__7_____6__28_____4____3__5___________';
  Tb[8] := '679835412123694758548217936416723895892561374735489621287956143961342587354178269';
  Tb[9] := '_______12__8_3___________4_12_5__________47___6_______5_7___3_____62_______1_____';
  Tb[10] := '346795812258431697971862543129576438835214769764389251517948326493627185682153974';
  Tb[11] := '_______12_4__5_________9____7_6__4_____1____________5_____875__6_1___3__2________';
  Tb[12] := '598463712742851639316729845175632498869145273423978156934287561681594327257316984';
  Tb[13] := '_______12_5_4____________3_7__6__4____1__________8____92____8_____51_7_______3___';
  Tb[14] := '364978512152436978879125634738651429691247385245389167923764851486512793517893246';
  Tb[15] := '_______123______6_____4____9_____5_______1_7__2__________35_4____14__8___6_______';
  Tb[16] := '649835712358217964172649385916784523834521679725963148287356491591472836463198257';
  Tb[17] := '_______125____8______7_____6__12____7_____45_____3_____3____8_____5__7___2_______';
  Tb[18] := '378694512564218397291753684643125978712869453859437261435971826186542739927386145';
  Tb[19] := '_______13___5___7____8_2______4__9__1_7____________2__89_____5__4____6______1____';
  Tb[20] := '572649813986531472314872596238457961167298345459163287893726154741385629625914738';
  Tb[21] := '_______13___7___6____5_8______4__8__1_6____________2__74_____5__2____4______1____';
  Tb[22] := '867942513254731968319568724532496871196827345478153296743689152621375489985214637';
  Tb[23] := '_______13___7___6____5_9______4__9__1_6____________2__74_____5__8____4______1____';
  Tb[24] := '967248513254731869318569724835426971126987345479153286743692158681375492592814637';
  Tb[25] := '_______13___8___7____5_2______4__9__1_7____________2__89_____5__4____6______1____';
  Tb[26] := '278649513956831472314572896532467981167298345489153267893726154741385629625914738';
  Tb[27] := '_______13_2_5______________1_3____7____8_2_____4_________34_5__67____2______1____';
  Tb[28] := '549728613328561497716493825183654972957832146264179358892347561671985234435216789';
  Tb[29] := '_______13_4_____8_2___6____9_6___4_____8________3______3_1__5______4_7_6_________';
  Tb[30] := '867459213549231687213768954986517432375824169421396875634172598158943726792685341';
  Tb[31] := '_______13_4_____9_2___7____6_7___4_____3________9______3_1__5______6_8_7_________';
  Tb[32] := '978654213546231798213879654697518432481326975325947186734182569159463827862795341';
  Tb[33] := '_______132__8_____3______7____2__6____1_______4__________4_15__68____2______7____';
  Tb[34] := '478526913219837456365149872793214685521968734846753129932481567687395241154672398';
  Tb[35] := '_______134__8_____2______7____4__9____1_______6__________5_16__38____2______7____';
  Tb[36] := '675924813413867592298153476732415968841396725569782134924531687387649251156278349';
  Tb[37] := '_______14____2____5_________1_8_4___7_____5_____1_________5_73___42______3____6__';
  Tb[38] := '976583214481629357523741869315874926749362581862195473198456732654237198237918645';
  Tb[39] := '_______14__8__5____2___________2_7_51______________8___7____53_6__14_______2_____';
  Tb[40] := '596782314318465279724319658943821765185976423267534891471698532652143987839257146';
  Tb[41] := '_______14__8__5____2___________2_8_51______________7___7____53_6__14_______2_____';
  Tb[42] := '596872314318465279724319658943721865167598423285634791471986532652143987839257146';
  Tb[43] := '_______14__8__9____2___________2_8_51______________7___7____93_6__14_______2_____';
  Tb[44] := '569872314318469257724315689943721865157986423286534791471658932692143578835297146';
  Tb[45] := '_______147___________5______9__14____5____72____6________9__8_56_____9__1________';
  Tb[46] := '538279614762148593914536287296714358451893726873652149347921865625487931189365472';
  Tb[47] := '_______1479__________2__________36_5__1____________2___6____73_2__14_______8_____';
  Tb[48] := '826375914795481326413269857942713685651928473387654291164592738238147569579836142';
  Tb[49] := '_______1497__________2__________36_5__1____________2___6____73_2__14_______8_____';
  Tb[50] := '826375914975481326413269857742913685651728493389654271164592738238147569597836142';


About the Gordon file on the site you can see that
HE HAS NOT GENERATE any grids he has only made a collection of all tyhe grid that he find. He can'nt make one!
But it's a good job for us

In the solveur I will integrate a real grid generator not a morph but it's in works. Working on the signature I found interresting implication so I hope to convert them in soft

The challenge given is today:
C. give me a valis grid. In fact a 19 clues solution and I have to find the clues!
Help me!!!!:!

For some programmer Solveur.exe is in Pascal Delphi 6.
Long live Pascal!!

how do you finf those 25 grids?

Papy

[coloin]

I have always admired the French style and flair, usually in Football and Rugby.

I think you will find that Gordon did indeed generate his collection - no one else could do it. I think I took a random grid and got an 18 - and I was pretty pleased with myself !

But you have given us two puzzles as an example and interchanged 3 clues.....but strangly it is not a simple clue swap

Code: Select all

+---+---+---+
|...|...|.1.|
|4..|...|...|
|.2.|...|...|
+---+---+---+
|...|.5.|4.7|
|..8|...|3..|
|..1|.9.|...|
+---+---+---+
|3..|4..|2..|
|.5.|1..|...|
|...|8.6|...|
+---+---+---+
  and grid solution
+---+---+---+
|693|784|512|
|487|512|936|
|125|963|874|
+---+---+---+
|932|651|487|
|568|247|391|
|741|398|625|
+---+---+---+
|319|475|268|
|856|129|743|
|274|836|159|      bands   22 377  33  , 371 370 130
+---+---+---+


+---+---+---+
|...|...|.1.|
|4..|...|...|
|.2.|...|...|
+---+---+---+
|...|.5.|6.4|
|..8|...|3..|
|..1|.9.|...|
+---+---+---+
|3..|4..|2..|
|.5.|1..|...|
|...|8.7|...|
+---+---+---+       
and grid solution
+---+---+---+
|793|684|512|
|486|512|937|
|125|973|846|
+---+---+---+
|932|751|684|
|578|246|391|
|641|398|725|
+---+---+---+
|319|465|278|
|857|129|463|
|264|837|159|
+---+---+---+     bands   26 359 222  , 371 370 130   

Well the grids are different - so they cant be morphs of each other !

There are a large number of 17 clue puzzles out there

Code: Select all

36628*9!*6^8*2 = 44649462705684480

So probably these two grids are not necessarily "new"

A little bit of work made 2 more

Code: Select all

.......1.4.........2...........5.7.4..8...3....1.9....3..4..2...5.1........8.6...
.......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6...
.......1.4.........2...........5.6.4..8...3....1.9....3..4..2...5.1........8.7...
.......1.4.........2...........5.4.6..8...3....1.9....3..4..2...5.1........8.7...

The grid solutions have all these clues in common

Code: Select all

+---+---+---+
|.93|.84|512|
|48.|512|93.|
|125|9.3|8..|
+---+---+---+
|932|.51|.8.|
|5.8|24.|391|
|.41|398|.25|
+---+---+---+
|319|4.5|2.8|
|85.|129|..3|
|2.4|83.|159|
+---+---+---+

They differ only in the 18 clue 2-rookery envolving the 6s and 7 clues and the unavoidable set {38,39,47,49,87,88}.

Await Gfroyle - he will put them thru' Nauty and see if the answer is >36628. I fully expect him to say...."been there done that !"

I admit the problem to find a 19 clue puzzle in the grid I posted is difficult - but it does have one ! -

Good luck

C

[gsf]

I
how do you finf those 25 grids?

the underlying concept here is isomorphism
in particular "equivalent up to isomorphism"
the signature you propose is not "equivalent up to isomorphism"

one method to determine equivalence is to use the nauty program
this is what gordon did to produce his catalog of puzzles
all 36K are different from each other
any claim to the contray is based on faulty data/algorithms

another is to devise a canonical form and use that form as a comparison key
this is what I did in my solver as an independent conformation of gordon's 36K 17's

here is a method to check for new 17 puzzles:
canonicalize the puzzle catalog (gordon's 17) and then canonicalize each
puzzle under question and see if its already in the catalog

solveur produced 50K puzzles
I canonicalized and sorted them and got 25 puzzles
I then checked if these were in gordn's 17 and they were
=> no new 17

the puzzles I posted were canonicalized
but they are equivalent to the ones in your program

it is fairly easy to devise signatures such that
signatue(A) != signature(B) => A != B
it is difficult to devise the converse

[gsf]

A little bit of work made 2 more

Code: Select all

.......1.4.........2...........5.7.4..8...3....1.9....3..4..2...5.1........8.6...
.......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6...
.......1.4.........2...........5.6.4..8...3....1.9....3..4..2...5.1........8.7...
.......1.4.........2...........5.4.6..8...3....1.9....3..4..2...5.1........8.7...

the two grids cited by papy (which are not equivalent) and these 4 are isomorphic to one of these two (in canonical form)

Code: Select all

......7.........1....2......3..79....6......2.....4..8..7..14..5.8........2....3.
.2.......4.............1..........57.3.....1.9...2..4...5.9......1...8.....64.3..


so no new 17 sudokus in this thread yet

[udosuk]

Here you a have two grids take in the gordon file (in the fisrt)
The morph is specialy easy to see

000000010
400000000
020000000
000050407
008000300
001090000
300400200
050100000
000806000


000000010
400000000
020000000
000050604
008000300
001090000
300400200
050100000
000807000

All the clues are the same EXCET a Tri permutation beetween 6 7 4 1
look for example at the last row the 6 and 7 are inverse wit the row 4
Yu have the same number of each value, the same nurepartition by row, box... It's the same grids but not the same Valid Soduko Grid

Although these 2 puzzles differ by only 3 clues, they're essentially different puzzles (not "morphs" of each other)... All ~36,000 of Gordon's puzzles are essentially different...

But gsf has found that all ~50,000 of 17-clue puzzles you claimed to have generated are in fact all "essentially-same morphs" of a total of 25 basic samples, which in fact had all been discovered by Gordon already ages ago...

Perhaps you should pay attention about ways 2 puzzles could be "essentially-same"... Besides permuting the numerical values we could also exchange rows/columns/bands/stacks, plus rotations & reflections...

[Papy]

But you make a mistake:
the two grids are equivalent
they are not EQUAL but the same
When we calcule permutation you don't care of the value
and in the sodoku the number of combinations is limited
but not the original grid.More exactely the number of combination is
limited but the grid are unlimited.
Perhaps that I make a mistake when I think that each valis grid can receive all combination
but it's sure that every grid can receive 17 clues

The works on the goron file is not ended
For example take the file, put all the clue at the same value
and compute how many different combination you have
Compute the different repartition of the value...
You always add small values.

It will be interressing ti know how Gordon select the file
How did he said that the two sample are not equal?


I do think that my theoru have to be modifiy Is't the beginning!
But is clear that hat is an other approch

In my solver have try the Papy methof to solve?
With no recursive!
Have you specific algo to loiok if a disopsition is good

Not the same number in a rox,colon or box?
Papy

[Papy]

I have make a study of the gordon file and i give you the results
For you to make conclusion

First I take the file and change all the clues for a specific value

That give me
Problems with differents repartitions
After I compute How Many diusposition I found using the rows
Rows dispotitions
With colons
Colones dispotitions : 32
Wityh Boxes
Boxes dispotitions
With Number
Values dispotitions
After the repartition with this 3 physical set
Clues dispotitions
And Finally problem with specifics dispositions for each set

Code: Select all

Number of problems: 36627
Problems with differents repartitions: 23624
Rows dispotitions     : 31
Colones dispotitions : 32
Boxes dispotitions    : 28
Values dispotitions   : 71
Clues  dispotitions   : 1893
Total  dispotitions    : 10157


You have only 10157 differents totals dispsitions considering the value
So I was bad thinking that the value do not influence the solutions
The same disposition accept many valid grid
But the physical disposition of the clues can be use to generate problems
If we compute a dispotion which is in the 1893 it will be perhaps easy to found grid!

You all know!

Papy

[gsf]

Code: Select all

Number of problems: 36627
Problems with differents repartitions: 23624
Rows dispotitions     : 31
Colones dispotitions : 32
Boxes dispotitions    : 28
Values dispotitions   : 71
Clues  dispotitions   : 1893
Total  dispotitions    : 10157


papy, there are no duplicates up to isomorphism in gordon's catalog
you may concoct signatures or dispotitions that happen to be the same for two or more puzzles in the catalog,
but that does not (and cannot based on computations already done on the catalog) prove that the puzzles are equivalent

search for "canonical" in the player's and programmer's forums for background on
isomorphism, automorphism, and canonicalization

[udosuk]

But you make a mistake:
the two grids are equivalent
they are not EQUAL but the same...

I would like to know how gsf & coloin think... Who made a mistake there?
Papy, perhaps you could consider writing in French, and that get babelfish to translate your text... Perhaps we could understand your words easier...

[fermat]

But you make a mistake:
the two grids are equivalent
they are not EQUAL but the same...

I would like to know how gsf & coloin think... Who made a mistake there?
Papy, perhaps you could consider writing in French, and that get babelfish to translate your text... Perhaps we could understand your words easier...

I am in stiches laughing here. <I kid you not, I think I am bleeding!>

An actual person conversant in all our terminology could work.

[gsf]

But you make a mistake:
the two grids are equivalent
they are not EQUAL but the same...

I would like to know how gsf & coloin think... Who made a mistake there?

there are no duplicates in gordon's 36K 17 catalog
this has been verified by at least two different mathematically sound methods
papy's claims based on signatures and morphs are wrong
the signatures are weak in that they make different puzzles seem the same
and some of the morphs used to back the claims are impermissible

the permutations that leave a sudoku unchanged are:
(a) rotate the grid 90 degrees
(b) swap the top two rows
(c) swap the top two bands
(d) swap any two cell values for all cells with those values

all permissible permutations can be constructed from a combination of the above

finally, there is a language barrier that has hindered this thread
if we fall back to mathematics then statements like
the two grids are equivalent -- they are not EQUAL but the same
can be disambiguated to
the two grids are equivalent up to isomorphism
or
all of the puzzles in gordon's 36K catalog are different up to isomorphism

[coloin]

gsf is right

Interestingly on the subject of normalizing puzzles.....

I have noticed however that a large proportion of Gordon's 17 puzzles have this "equivalent" pattern inherent in the puzzle.

Code: Select all

+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|.6.|
+---+---+---+
|..7|...|...|
|...|..8|...|
|...|...|...|
+---+---+---+

sometimes only seven clues fit the pattern......and maybe its a coincidence.....but looking at random larger clue minimal puzzles I cant seem to see this pattern that often !

Of course we dont need more 17 puzzles but............even more interestingly Oceans 10.0 and 9.9 puzzles also have this 8-clue "inverse rookery/template"

Might this help in making hard puzzles ?

C

[Papy]

I don't know what is "canonicalize" but this method detect morphs
The Gordon file does not contains morhps

It's the state of the science:!

If the Gordon file does not contains morphs we call 'originals' the 36000 grids
The challenge for me is not to make morph but originals
For this I make a 'signature program'
This signature DETECT MORPH but also similar grid (for me)
Analysing the Gordon file I found 10157 originals FOR ME

But analysing the Gordon file is not the goal in itself. I want to find new
caracteristiques to genrate Sudoku

The result of the analyse are not useful while I don't find the connections beetwenn tha results!
Perhaps I never found. Today I think that exploration is not ended so I work
If tomorow exploration end also I stop my research.
That all.
Speaking of it with you give me other analyses: the echange is positif
(I hope for you and me). For me ist's sure I learn

I want to learn more on 'canonicalize'.
I understand the goal but not the method if someone can explain it me, indicates piblic software, sources I 'm VERY interressing.
Thanks
Papy

[Papy]

Why this Grids are FOR ME the same?
An other time: the Gordon works is good and his file is useful for me. Thanks
If some one is blessed by my words: Sorry.
I have a new theory that doesn’t mean that the others are bad or that my theory is true.
But:

I have selected two grids in the Gordon files

_3_ ___ _7_ ___ 9_4 ___
___ 5__ _9_ ___ ___ __2
___ 1__ ___ ___ ___ 7__

_8_ _7_ 2__ ___ 8__ 34_
___ __3 5__ 5_2 ___ ___
___ ___ 1_6 7__ ___ ___

1_5 6__ ___ ___ _76 1__
9__ ___ ___ ___ 52_ ___
___ _4_ ___ _3_ __ _ 9_

1- The rows Compute the number of clue on each row

2 2 1 3 2 2 3 1 1 2 1 1 3 2 1 3 2 2
1 1 1 2 2 2 2 3 3 1 1 1 2 2 2 2 3 3

2 The columns Compute the number of clue on each column

2 2 1 3 2 1 3 2 1 2 1 1 3 2 2 3 2 1
1 1 1 2 2 2 2 3 3 1 1 1 2 2 2 2 3 3

3- The Boxes Compute the number of clue on each box

1 2 2 1 2 4 3 2 0 0 2 2 3 1 2 1 4 2
0 1 1 2 2 2 2 3 4 0 1 1 2 2 2 2 3 4


4- The number Compute the number of clue for each vcalue
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
3 1 2 1 3 2 2 1 2 1 2 2 2 2 1 3 1 2

1 1 1 2 2 2 2 3 3 1 1 1 2 2 2 2 3 3

Always identical! And after?

We study the value it’s easier
Permute the value en you will get the same repartition for each number
The Sudoku is the same
We can do the same with boxes, rows and columns
If you look at the boxes you can see an empty box. On each grid
Only permutations to pass from grid one to grid 2


Rows dispotitions : 31
Colones dispotitions : 32
Boxes dispotitions : 28

I don't know why but it seems that rows,columns and boxes seems to be limited to 32 2^5

Values dispotitions : 71
Why? Perhaps because you don' have 9 elements to permute but the same number that the clues : here 17 so it seems normal that you have more repartitions

So what is wrong in this argument?

Thank for the stimulation that you give me!
It's not easy in my wheel chair to meet other fans!!!

Papy

[gsf]

The challenge for me is not to make morph but originals
For this I make a 'signature program'
This signature DETECT MORPH but also similar grid (for me)
Analysing the Gordon file I found 10157 originals FOR ME

using "the number of cells with i candidates (pencilmarks)" for i = 1 .. 9 as a signature
produces 22567 different signatures

I want to learn more on 'canonicalize'.
I understand the goal but not the method if someone can explain it me, indicates piblic software, sources I 'm VERY interressing.

check this thread http://www.setbb.com/sudoku/viewtopic.php?t=795&highlight=canonical&mforum=sudoku
its long but exposes another learning experience
and LummoxJR provides a good explanation near the end