New challenge

Programs which generate, solve, and analyze Sudoku puzzles

New challenge

Postby Papy » Thu Aug 17, 2006 9:03 pm

Hi every one
sorry for my poor english but Sudoku is internationnal
I 'm a french programmer and a new sudokiste
Like many I write my own solver and generator.
Necesessary they are the best one:)
( Princess Leila tell me that in episode 8)

I program nacked pairs, X wing like thousand programmers
But the challenge is not complex: you have a list of techniques, well explained and you just have to code them.

So I try to find new challenge. Going on the Gordon site to get 36600 17 clues grids to try to make thefirst 16 clues grid of the worrld
Gordon says:
Starting from a grid you can make a lot of permutations, rotations, inversions... with rows, blocks, colonns... It's true

And the result is very different of the original grid.
And he said 'In my list there no such grid'. All the grids are original!

I ask him the question How he does?
But he is perhaps in holiday or with his baby

So I don't know the method. I have begin to search on the net but I don't found a forum or an idea.

So I code a first version of my solution
But it's not perfect so I imagine to ask the question to everybody
Contacting the moderateur of this forum he accept that I subpmit to you the challenge

t's just a game not a competition to say 'I am beter' Like Olympique games the interet is participate not win! (but win is good!)
Searching first elements to begin an idea have appair:
If we can find a original grids after a big checker we can use the technique to sign the grid. The interest is just to say: It's my baby. I work hard to make the first 16 clues grid with only one number reveled!

You don't have to be coder to participate The idea of every one could be THE idea.

To begin the tropic I give you the state of my work and the way I choose.
To work i got the Gordon collectio with 17 clues (the minimum)

( Just for the fun I run my solver : All the grids are godd I HAVE the 36600 solutions)(three or four hours)

In fact when you have a grid you can begin by forget the latin square. You don't have it yet. So you have to deal with the clues
The clues are in a 9x9 matrix 9 rows and 9 colons
to acces to one cell of the grid you need 18 diferents values. The first case of R1 and C1 is common so you have 17 reference: It's the explication why you never find a 16 clues grid: you cannot acces to every cells!

So we can considere that each cell of the grid will be acces by XY coordonnates. f(1,1) give for example a 3 in the R1C1. So he first control that we can do is to verifie that each cell is XY accessible. If not the sudoku will be bad.

I heard the firsts voices : Yes but if you have an empty row or empty colon??How to access.

I will not tell you all today. Search with me....

Papy

I hope that this challenge will give you fun
I leave on the border of the sea so SSS
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Fri Aug 18, 2006 10:10 am

I think I understand your challange and I agree with your sentimentss.

Why dont you start a "Min number of clues-2" thread in the General/puzzle section.

A wade through Min number of clues should enlighten you - I hope it doesnt discourage you.
regards

Whats your plan ?
C.
coloin
 
Posts: 1637
Joined: 05 May 2005

Minimum

Postby Papy » Fri Aug 18, 2006 11:35 am

That is not the goal of this challenge
In fact the probleme behind the original grid is the unique solution

I know that a lot of people look afeter the 16 clues: for me me it's the 'philosophical stone' This grid does'nt exit not bescause we don't found it
but like I try to explain it: to acces to eache celle of a matrix you need
the number of row+ the number of colonne-1
I 'm not a mathematicien but I think that the demonstration is easy.

To the challenge the idea is to find caracteristiques unique for a given grid:
the caracteristiques will not be unique but the combinaison of 3,4,5... will be unique
I think that we have to choose one grid for working and example
this grid for example(found on the forum;)


Code: Select all
 . 9 8 | . . . | . . .
 . . . | . 7 . | . . .
 . . . | . 1 5 | . . .
 1 . . | . . . | . . .
 . . . | 2 . . | . . 9
 . . . | 9 . 6 | . 8 2
 . . . | . . . | . 3 .
 5 . 1 | . . . | . . .
 . . . | 4 . . | . 2 .

 

Now we compute howmaany clues on each line, row and box
2,1,2,1,2,4,3,2,2
2,1,2,3,2,2,0,3,2
2,3,0,1,3,3,2,1,2

If I compute welle the three summs are 17 the numbers of clues

So using this 3 serials we can gegin to identyifie all the using the same disposition of the clues
you can permute row,colonne,blocs, row you will always have the sames value(you have just to sort them)
1,1,2,2,2,2,2,3,4

in fact if you check a grid you NEVER change this values!
The permutation always works on entire(9) set of cell
Try...


Papy
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Fri Aug 18, 2006 3:59 pm

I think I understand you....
You have counted the number of clues in the respective columns/rows/boxes and the individual clue frequency.

Gfroyle and Ocean looked at the boxes and clue frequencies in a series of 17 clue puzzles here

Gfroyle found the 17s by recursivly going through iterations in 18 clue puzzles, the incidence of 17s is 1in 100,000 grids, and finding a 17 in any one grid [known to have a 17 is] tricky !. He excluded morhologically similar puzzles - each puzzle has 9!*72^2 morphs]

But there is a lot going on in every grid that is not immediately apparent [understatement] !

For a start there are 6*10^21 grids [include 9! * 72^2][relabelling and row/column/box shuffling]

There are possibly as much as 10^14 individual minimal puzzles [clue range 17 to 35] which uniquely define each of the 6*10^21 grids.

There are also many unavoidable sets in every grid. see unique solution

Each unique puzzle has to have at least one clue in each unavoidable set.

It is amazing that almost every grid has a 19 clue puzzle in it [somewhere]

RW and I are presently working on "the structure of the solution grid"

Regards

I could use your help in modifying my programs - as my mentor lost enthusiasm !

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Empty set

Postby Papy » Fri Aug 18, 2006 8:04 pm

I don't understanbd
Each unique puzzle has to have at least one clue in each unavoidable set.
It is amazing that almost every grid has a 19 clue puzzle in it [somewhere]


1-- Many grids have empty set! What do you want to tell me?
2- Whith ALL the grid you can buil puzzle with 17 -18-19....

All latin square are mathematicly equivalent the: same number of each digit, of set so Every sqaure can have a 17 clues puzzle.


Make the inverse

Take a 17 clues and had clues...
you will have unique solution and valid puzzle

You can also analysing your collection of grids and extract like I do on Gordon file the disosition of the clues taking care of permutation: only 17!!!!!! with 36000 puzzle

If you try this 17 dispositions on a Latin square I tbink( I Have not try yet) that find one good .Be careful about the digit them self they multiply
I hink that can be a good trip:

Choose a latin square publish it and ask for making sudoku with.
We sure have 17-18-25 clues...

Papy
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Fri Aug 18, 2006 8:40 pm

Papy wrote:1-- Many grids have empty set! What do you want to tell me?


Well ...if there is an empty set without a given clue in it ...it has multiple solutions !

OK, try and solve this one......
Code: Select all
+---+---+---+
|..6|347|598|
|458|169|732|
|379|285|461|
+---+---+---+
|..3|478|659|
|584|692|317|
|697|513|824|
+---+---+---+
|732|851|946|
|845|926|173|
|961|734|285|
+---+---+---+  you cant because there are 2 solutions !

+---+---+---+
|12.|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|21.|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+   the unavoidable set is [11,12,41,42] or [r1c1,r1c2,r4c1,r4c2]
+---+---+---+
|126|347|598|
|458|169|732|
|379|285|461|
+---+---+---+
|213|478|659|
|584|692|317|
|697|513|824|
+---+---+---+
|732|851|946|
|845|926|173|
|961|734|285|
+---+---+---+   or

+---+---+---+
|216|347|598|
|458|169|732|
|379|285|461|
+---+---+---+
|123|478|659|
|584|692|317|
|697|513|824|
+---+---+---+
|732|851|946|
|845|926|173|
|961|734|285|
+---+---+---+


using this as a text string
Code: Select all
216347598458169732379285461123478659584692317697513824732851946845926173961734285

run nppcsu.exe and this will give you plenty more unavoidable sets - each set needs one clue for there to be a unique solution.

Papy wrote:Choose a latin square publish it and ask for making sudoku with.

Code: Select all
123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678


Regards
C
coloin
 
Posts: 1637
Joined: 05 May 2005

Latin Square

Postby Papy » Fri Aug 18, 2006 9:37 pm

We don't speak of the same square!

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678


A magic square is a square where all the row and all the colons have the same sum

http://fr.wikipedia.org/wiki/Carr%C3%A9_magique_(math%C3%A9matiques)

A valid square for sudoku have also the same sum for t-he box

It a set of nine magic squares ordrer 3 !


The solution of a sudoku can support any puzzle you want.17..30 clues

That is what I think!:)

If you want I have a generator for sudoku valid square


040806900
105000000
000000020
000008060
000700003
800000000
000090000
000070000
051000000
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Tue Aug 22, 2006 10:21 am

Papy wrote:I have wriiten a Valid Gid and 17 clues Sudohu generator
Are sone people interrested to TEST it?
http://rapidshare.de/files/30182806/Solveur.exe.html


I have downloaded this program

you need to make a file called in "c:/Grilles/Australie.txt"

Otherwise it works !

Question to "John Fullspeed"

Are you taking random files and generating 17s ?

or are you using Gordons 17s and generating morph puzzles ?

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Boris Solver

Postby Papy » Tue Aug 22, 2006 10:40 am

Hi C
I not using only gordon file but yes I generate moprh but I have
2000 originals!

The software change:
Now you have

- a function to find mophs!
You give it the godon file in entrance and it tell you wich are the same!!!
(At the speed of John!!!)
-a function the verify unique solution
(Not always veru speed sometime 3 mn)
-a function the detect minimal Sudoku(with a valid sudoku it gives unused clues!!!
(Time depending of the original number of clues)

But I have the challenge in my mind: make a 17 clues sudoku with your
19 clues solution!
I think that I found the way to generate a 17,18.. Sudoku on ALL Valid Grid!!!

I controle the app to remove annexed files and I will give you the link.

Papy Fullspeed.
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Tue Aug 22, 2006 11:13 am

Great - i will update it.

On your 17s.........I await Gfroyle's analysis to see if there really are new ones.

This is the grid which we struggled to, but eventually got a 19 in !
Code: Select all
325681974641379258789425613134968725962537841857142396416293587273854169598716432

I will run checker to see if it has a 18 !

Not all grids have 18s....[or 19s] I believe you will find.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby gsf » Tue Aug 22, 2006 3:37 pm

ok, time for a reality check
out of the blue someone claims to have a program that in <10sec produces 50K 17 clue 9x9 sudoku
and it took gordon how long to generate 36K?

its a tough translate (deciphering some of my msgs can be tough too)
I'm fairly certain papy snarfed a few (25 to be exact) of gordons 36K
and then permuted these by the well known isomorphism preserving sudoku transforms
to produce the 50K dropped by Solveur.exe

here are the 25 in box canonical form (top left box in row/col order, lexicographic minimum)
Code: Select all
........9...1..23.78.6......6.....7..4..9........24...3...........8...6...2......
......7.........1....2......3..79....6......2.....4..8..7..14..5.8........2....3.
......7.94.....1.....2......1.........7..2.6....5.4.2.3......5.....7.8...9.......
.....6......7.......91..5..2.5.4........9...3.......7..4..........32.8..67.......
.....6.8.45.......7............4......81...9.......2....1...46...23.5...........7
....5....4.......3..9..1.....7...95...83........6...7.31.......6......1.....7....
...4.......6.....2.8..3.....9....84..7...2........59..3.2.........9.......5...3..
...45......6.....7.8..........7.3..854......29.........7...8..........5......6.9.
...45......6...2.....3..........19..3.4...........6.7...28.9....9......3........5
...45......61.......9............7...4....81......6...37..4.......8...96........2
..3....8..56..........1...421..7.............9..6...5....5........3.....8.....1.7
..3...7.9............2.1...2...9..1......7........4....4.....2..7.6........3...51
..34..7.......91.......2......67...3....1....9.5....4..........67..............25
.2.......4.............1..........57.3.....1.9...2..4...5.9......1...8.....64.3..
1...5............3.8.....4.2....4...5.4..............7.....62...7.8.3....9....5..
1...5....4...........36.....3....95........2......1.......9.4.1.627.............8
1...5..8...6...........3....3........9....4.....18..5......92..8...........6.43..
1..4.7.....6....23........5....914.......6....3...............6...32....8.7......
1..45......6....37...2...........5..6.7......8.....4...4...........81.6......3...
1.3.............7...9....4...5.74........6...8.....3.2...2........59.1...4.......
1.3...........8..2..9....4..4....8.5...9........1..............87...4....6.3...1.
1.3..........8...7..9.....5..5...19..4...........2.3...7......2...9.4......3.....
1.3.5......6...1.....2...4....8.49.....9.......5.....3....2............594.......
12...7....5......3.....6..4...84..1..6...........3........1.9.......27....4......
12..5...........73.8.........7.....6.............12......6..8.2......1..9.57.....


papy, a few messages back you claim to have a signature that uniquely
identifies 17 clue sudoku -- could you compute the signatures for gordon's
17's and post two puzzles from that collection with the same signature?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Sol veur

Postby Papy » Tue Aug 22, 2006 3:49 pm

New version

http://rapidshare.de/files/30353581/Solveur.zip.html

Sorry I don't well understood the mailIU have to translate i

But this new version analyse the Gordon file and show you that 'only' 9900 files are original 25000 are morphs

The software make a file with all original not morph
So i post you two grids (morph for me)
Grids with the solution

I will explain you why they are simila (not all it's my secret!!!)
Papy
 
Posts: 131
Joined: 15 August 2006

Re: Sol veur

Postby gsf » Tue Aug 22, 2006 4:22 pm

this solveur version lists the puzzles claimed to be unique but gives no reason
(should be in Morph.log but that file is not created)

could you pick any two puzzles from gordon's 17 that have the same signature and post the puzzles along with the signature?
thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Morph

Postby Papy » Tue Aug 22, 2006 4:22 pm

000000010400000000020000000000050407008000300001090000300400200050100000000806000
000000010400000000020000000000008000300001090000300400200050100000000807000


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
Look in the problem you have

Look in each problem you have
1 time the 6 and 7 and 3 times the 4
changing the place we do'nt change the number => the problem

693784512487512936125963874932651487568247391741398625319475268856129743274836159
793684512486512937125973846932751684578246391641398725319465278857129463264837159



Take the first replace the 6 by the 7
invert R4 C7 R4 C9 = grid 2


Replace now the 3 by the 9 the 8 by the 1 and you got an other morph!
invert row 1 etn 2 colon 7and 9 you still have a valid morph!

It's the same but plaisir is equal!
It's a very easy sample we can make complex permutation
If some one is interested I can prepare a tread on the permutation

Papy
Papy
 
Posts: 131
Joined: 15 August 2006

Gif

Postby Papy » Tue Aug 22, 2006 4:31 pm

For the log I don't know what to write in !!!

For mr grids are equals when they have the same repartition into th
rows,the colons,the box and the value

I have take 1 grid make a MILLIONS of morhs
and all the grids have the same signature!!!
And is't normal!

I don't says or think that it's he method used tto build it but
you have not 1 millions og 17 clues grids on a valid grid
only 2000 to 3000 so is normazl thant we find the same!

My Generator 17 make morph : do you see it ? Are the Sudoku more easyer?
Papy




s
Papy
 
Posts: 131
Joined: 15 August 2006

Next

Return to Software