Impossible is not French!

Everything about Sudoku that doesn't fit in one of the other sections

Impossible is not French!

Postby Papy » Mon Nov 20, 2006 3:21 pm

Another approach of Sudoku:
This approach does not seek to be better than another only with being different. The goal being to seek to know why one 17 revealed is valid and not another.
Rather than to stick to the usual mathematical concepts we will take the basic data-processing step: What seeks one has to obtain and how y to arrive
What we want to obtain is a whole of 17 digits ranging between 1 and 9 included and puts it which contains this value. Our boxes being represented by a plate of 9x9 is 81 boxes.
1-5,3-12,1-11 9-25,8-42.....
It is important to note that behind this simple result hides constraints which can have a complexity and the number which they wish: that does not even influence the result in him. The result will be simply good or bad.
The principal constraints are, point out it, a figure are present only once by column, line, or limp. And the problem accepts only one and single solution. With that with us to play.
For us if one of these conditions is not filled the grid is bad.
For our work we used the collection of Gordon, available on Internet and which does not gather less than 36628 different grids with 17 revealed each one. We thank it for this work which we analyzed as it proposes it on its site. I also hold has to thank gsf for his solver groove: splendid work! A grid of Sudoku actually made up of two information by is revealed: its position( the cell) and its value (the figure which it contains).

Each one of these components is of the same importance: one or the other has suddenly missed and the problem becomes impossible: Take an unspecified grid and to change place one of randomly revealed: the problem becomes impossible. Pareillement if you to modify the value of one revealed the problem becomes also (except chance) impossible.

We were interested today in the position of révèlés. Same work must be made on the figures to complete to bore the mysteries of the 17 révèlés By studying the characteristics of those we retained three of them which seemed easy to us to apprehend: the number of revealed for each column, each line and each limps

Thus for each grid we obtained 9 digits corresponding on the whole of each 9 column, 9 for the lines and 9 for limp. To avoid all the doubled blooms and other isomorphs we sorted these series of figures. A first thing has surprised us: their low number For 36000 problems we have only 31 provisions of columns, an equivalent number for the lines and only 20 for boxes. Strange.

It is clear that the series of the columns and the lines were to be identical: a simple rotation of 90° of each grid reversed these two values. To regulate this problem we made the union of these troiis series. New surprise the total of the new unit is 35! The mathematicians and data processing specialists must be surprised: 35 is not a particular value, even not a square. It is right 7 times 5. The mystery is complete
The first interesting conclusion is that if the provision of revealed on your grid does not correspond to one of that which is referred your problem is probably impossible. On the basis of this constation and deduction we can deduce from it that the possible number of provisions will be equal to 35*35*35 is 42875 different provisions.
i/e numbers has a reasonable data-processing dimension and one can imagine to generate them very to test the values of the boxes afterwards. But we can analyze even more this result if for each grid we have one of the 42870 provisions us should find them or at least largely in our reference frame.
Thus we go identified each one of the grid by three series of nine digits each one, each series being sorted before being placed behind the preceding one. For example 111222233, 111222233, 112222223 will give 111222233111222233112222223
the verdict is without call 1264 configurations different only with 36600 grids the report/ratio is surprising. But there too the direct conclusion is that if your distribution is not among those not safety.
It is true at this time but at all final: nothing shows us that the number is limited to 1264!!!! It is the number of our study not globality of the grids But still the our computers are not powerful enough. To test only one provision It will largely take us a day.
Then even 10000 days and we will be old. With this first approach we will be able to work on a smaller reference frame. It is which the easy way is which enabled me to put the hand on all these grids!!!
They were there and awaited our goodwill. If we take two grids with the same provision of clue only the digits change. While looking at our collection one realizes that sometimes only one figure varies from one grid to another BANCO!!!

We will take each grid and to vary the figures ONE by ONE from 1 to 9 for 17 reveal is
17*9 = 153 grids and if we put of with dimensions these new grids to make them undergo the same treatment we have to create a generator! After it ` does not remain to us more but à' to test all the possible combinations: one replaces the first clue by 1 and one seeks the solution, one puts one 2 and one starts again....
The method is brutal but it does not let pass any case. And for this kind of work we have our computers. A few hours of calculation will be enough
We have just made pass our reference frame of 36628 to.....! Not only the grids lose of their mystery but their known number increases considerably. Our work consisted of the enrichment of our collection by the contribution of new provisions of the figures of not revealed

We did not answer our question: 1264 it is the maximum of provisions?
Of course NO
To be continue....

Posts: 131
Joined: 15 August 2006

Postby coloin » Tue Nov 21, 2006 11:06 am

Maintenant, assez parle de cela la hypothese !

[Right much for the theory !]

Avez vous fabricez du neuveux dix-sept puzzles ?

"La preuve est dans le pudding !"

Posts: 1891
Joined: 05 May 2005

Postby gsf » Tue Nov 21, 2006 11:37 am

coloin wrote:Maintenant, assez parle de cela la hypothese !

[Right much for the theory !]

Avez vous fabricez du neuveux dix-sept puzzles ?

"La preuve est dans le pudding !"

hey, sudoku as a language learning aid
2014 Supporter
Posts: 7306
Joined: 21 September 2005
Location: NJ USA


Postby Papy » Tue Nov 21, 2006 1:32 pm

Load the link !!!!!

My little finger says me:

What? All these grids are goods?

I tes them whith the gsf solver
and it's the beginning

If the linf is invalid tell it me
Posts: 131
Joined: 15 August 2006

Re: Impossible is not French!

Postby ab » Tue Nov 21, 2006 2:27 pm

If you put it without a colon in front of it, it becomes a hyperlink!
but it says you've deleted the file! So the link doesn't work.
Posts: 451
Joined: 06 September 2005

Re: Impossible is not French!

Postby udosuk » Tue Nov 21, 2006 4:26 pm

ab wrote:If you put it without a colon in front of it, it becomes a hyperlink!
but it says you've deleted the file! So the link doesn't work.

Geez, this is what happens when a non-English speaker use a service targeted for English speakers... (Mind you, the Rapidshare company was initially based in Germany... They should give instructions in all European languages...:( )

You see, after you upload a file on rapidshare, they'll give you 2 links, which are like these 2 for say, Papy's file:

The first link allows you to download the file. The second link allows you to delete that file (the "killcode" act as the "password" to do so). So, the uploader was supposed to save the 2nd link secretly and only use it when he/she decides to kill the file. By posting it in public anyone can delete the file by accessing that url...:!:

So my guess is, either Papy deleted the file (accidentally) by clicking that "killcode" link himself, or the first user who managed to access that url (possibly ab) deleted it...
Posts: 2698
Joined: 17 July 2005

Return to General