|
View previous topic :: View next topic |
Author |
Message |
| ChPicard
| Joined: 12 Mar 2008 | Posts: 82 | : | Location: Montreal, Canada | Items |
|
Posted: Sat Apr 05, 2008 9:27 am Post subject: Quest for THE 16 GIVEN SUDOKU |
|
|
Hello
It is 4 am and I don't sleep because of the 16 given sudoku.
My computer is tired to search it but continues quietly its quest.
Yesterday I solved with a pencil a very easy 17 given sudoku by Andrew Stuart. It was so easy, I was sure than with one given less, it would be only a little harder.
This night, I tried to find a gap between 2 consecutives 17 given sudokus from the Gordon Royle's list but nothing appeared.
This weekend I will try to see if the position of the givens in a box has an importance. Solving by hand a puzzle, I noticed than a line of 3 givens in a box seems to give more restrictions than a wedge:
XX and XXX
X
In this forum, I saw statistics about the number of givens in boxes, patterns but not about empty rows or empty columns.
Finally I am hoping than Glenn Fowler or Kohei Noshita will find the beauty.
Courageously I am looking for other constructive ideas.
Good night everybody.
Jean-Pierre Sangin
Last edited by ChPicard on Sun Apr 06, 2008 12:21 pm; edited 1 time in total |
|
Back to top |
|
|
| Adak
| Joined: 27 Feb 2008 | Posts: 87 | : | | Items |
|
Posted: Sat Apr 05, 2008 10:15 pm Post subject: |
|
|
Jean-Pierre, are you searching through every possible 16 given grid?
If not, why not start from there, and let the computer do the work - and you can sleep, knowing that EVERY possible 16 given grid, has been tried.
If you'd like some computer power to help through this, let me know. I got some!
Adak |
|
Back to top |
|
|
| ChPicard
| Joined: 12 Mar 2008 | Posts: 82 | : | Location: Montreal, Canada | Items |
|
Posted: Sat Apr 05, 2008 11:17 pm Post subject: Who can confirm? |
|
|
Adak wrote: | EVERY possible 16 given grid, has been tried
Adak |
Ok Adak. Who can confirm?
Do you know each day, someone discovers a new 17 given sudoku?
Is it more difficult to find this? |
|
Back to top |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Sun Apr 06, 2008 1:00 am Post subject: |
|
|
Adak wrote: | Jean-Pierre, are you searching through every possible 16 given grid?
If not, why not start from there, and let the computer do the work - and you can sleep, knowing that EVERY possible 16 given grid, has been tried.
If you'd like some computer power to help through this, let me know. I got some!
|
ok, time for some back of the envelope calculations
(I sure hope there's at least one college course left that still teaches that)
there are ~5*10^9 unique solution grids
so even if you picked just one 16 from each solution grid
you would have to check ~5*10^9 16s for minimality
the best backtrack solvers can solve ~5*10^3 puzzles/sec/Ghz
lets assume 10^4 puz/sec/Ghz
and 10Ghz (maybe a multiheaded pentium)
so one machine might be able to check 10^5 puz/sec
5*10^9 puz / 10^5 puz/sec = 5*10^5 sec
that's about 5 days to check 1 16 from each of the 5B solution grids
suppose there were some other optimizations to get it down to 1 day to check 5B 16s
but that's only 1 16 per solution grid
there are many more than that
given that there are some 16 clue combinations that would never be minimal
e.g., 8 clues in one row/col/box
suppose you could rule out a bunch of combinations and only have to check
40 clues taken 16 at a time (40 take 16)
that's still 6*10^8 16s per grid
averaging over all grids and that comes to ~10^18 puzzles to check
or 10^8 days for 1 machine |
|
Back to top |
|
|
| Adak
| Joined: 27 Feb 2008 | Posts: 87 | : | | Items |
|
Posted: Sun Apr 06, 2008 11:42 am Post subject: |
|
|
Thanks for the into to the size of the search space, gsf!
If there is a project that will exhaustively and completely cover the 16 givens for a unique Sudoku puzzle, I believe that would be worth supporting, and I believe others would also join in.
I'm caught in the middle because I don't really have full confidence in the "let's work from the 17's to find a 16", and I certainly don't support the "let's start a search project that will start with the 12's".
Of course it's too computationally intensive to just have one machine work on it, that's clear. It might not need to be a full-bore distributed computer project, (ala BOINC), but that idea sounds attractive, for a project this size.
Jean-Pierre certainly has a lot of enthusiasm for this, but I was wondering who might serve as an overall advisor for this?
Does (gsf) any (gsf) names (gsf) come (gsf) to (gsf) mind?
|
|
Back to top |
|
|
| coloin
| Joined: 05 May 2005 | Posts: 97 | : | | Items |
|
Posted: Sun Apr 06, 2008 3:22 pm Post subject: |
|
|
I think gsf has tried, and i'm sorry to say almost certainly realizes that a valid 16 puzzle doesnt exist......
We have searched for new 17s for some time now, gradually getting better and better.........the more remote ones have not been found yet. However if there was a 16 it would have 65 non-minimal 17s and 6080 non-minimal 18s. These have not been found.
Having said that we thought we had found most of them @ 40000, now it is pushing 50000 different 17-puzzles.
Most solution grids have a 19 in them, 1 in 10 have an 18 and 1 in 100000 have a 17.
Puzzles tend to have 9! * 6^8 * 2 isomorphs......this makes it problematic to compare two different puzzles.
A canonicalized list in minlex order allows for a search "between" puzzles but realistically anything more than 14 plus 3 clues is too much. Even so this can be reduced by a number of constant clues in minlex grids.
The new 17s made by gsf are found by reducing a large set of random 21 or 22 clue puzzles to 18 clues and sometimes finding a 17. I believe he has several computors working effeciently in the background.......finding 1 new 17 per day.
We were very grateful to Anon17 who proved us with 5000 new puzzles at the 40000 mark ! He has a very optimized program !
Im not sure when or if or how we are going to know if we have found the last one...........if we can show this, then we know there is no 16-puzzle !
C |
|
Back to top |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Sun Apr 06, 2008 6:49 pm Post subject: |
|
|
There are 5.472.730.538 unique sudoku grids.
On each of them one must try out any valid 16-given pattern.
If no 16 given sudoku exists, than all combinations will result in multiple solutions.
What is a valid 16-given pattern ?
There are some restrictions:
-more than one empty row in the same band is not allowed
-more than one empty column in the same stack is not allowed
-more than four empty boxes are not allowed
Maybe there are more restrictions...
Now, how to split the search over multiple users ?
I remember that i used to participate in the SETI (Search for Extra Terrestial Intelligence) project years ago. A server was coordinating/dealing parts of recorded "noise" from outta space, to participating users, to lend their computer time. A programm on each user's PC was scanning the noise for repeating patterns, as possible evidence for the existence of extra terrestial intelligent lifeforms. I don't think they ever find something useable, but it's the same principle that could be used in the search for the 16 given sudoku....
Is there anyone who has the skills to let random users participate in the search whenever they are on-line with some sort of a programm that runs on the background, all coordinated by a server-programm ? _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
Back to top |
|
|
| coloin
| Joined: 05 May 2005 | Posts: 97 | : | | Items |
|
Posted: Sun Apr 06, 2008 11:03 pm Post subject: |
|
|
Good luck
http://math.ie/checker.html as mentioned is a program which will check for a 16 in a solution grid.
command is
c:\checker>checker128 testgrid.txt 16
This testgrid can be checked :
Code: | 792685341154329678368417295541876923879234156623951487415762839237198564986543712 |
Code: | Finished. Total computation time was 0d 00h 36m.
A full search was done (all puzzles were enumerated). |
No 16-puzzle exists for this grid (all puzzles were solved).This is possibly an average grid - depending on the MCN of the grid it could be a few minutes, sometimes more like days.
So 3000 million computor hours !
Is this quicker than projected with "Project Sudoku"
It would also be quicker than say picking a pattern of 7 clues [is there one ?] the equivalent of which always occurs in every puzzle, and then trying all the ways of adding 9 more clues. [? approx 10^17 combinations]
The reductions which have been suggested, together with combinations which cant be minimal, I dont believe are incooporated into checker.
Two empty rows in a band is an 18 clue unavoidable set, as is the absense of 2 clue values reveals another 18 clue unavoidable set.
C |
|
Back to top |
|
|
| Adak
| Joined: 27 Feb 2008 | Posts: 87 | : | | Items |
|
Posted: Mon Apr 07, 2008 1:21 am Post subject: |
|
|
The above describes exactly why I believe the Sudoku Project will never finish up through the 16's - they'll peter out long before they reach the 16's, imo. They refuse to talk about projected finish dates. IMO, they'll never get through the 16's.
The Sudoku Project has very few members, and most of them have an RAC (recent average credit) that is very low, indeed. Many are next to nothing, in fact, (0.25 or such). Most teams are just one or two people. That's pathetic. A decent C2D will easily earn 1500 RAC, after a week, and keep that average.
That's why I believe we could put together such a group, using BOINC, and concentrating just on the possibility of a given 16 grid, being a valid Sudoku puzzle.
Having said that, if the search space of the 16's has or is currently being completely covered by the current work on the 17's, then let's forget about this effort. I have no interest in re-doing a large analysis, that has already been done/or is currently being completed.
If there are significant gaps, or the current effort is not able to get enough computer power to complete this in a reasonable amount of time, then let's either assist them in their efforts, or start a new DC effort.
BOINC is the new and preferred Distributed Computing client. It's quite sophisticated, and is what most DC projects, including SETI, and The Sudoku Project, use. I was just using it a few months back, for a SETI gauntlet (a type of SETI short term race), contest, and it was impressive.
Opinions most welcome. |
|
Back to top |
|
|
| Adak
| Joined: 27 Feb 2008 | Posts: 87 | : | | Items |
|
Posted: Mon Apr 07, 2008 1:53 am Post subject: |
|
|
This is *exactly* the kind of thing that drives me crazy with the 16's search,
(from the Checker website):
Quote: |
(We have not actually proved that we find all unavoidable sets of size up to 12, but we believe this to be true.)
|
So they haven't proved a central concept to their Checker, and then they use several other binaries, that probably haven't been really well tested, either, and then they use Gunther's program to do something else, and God only knows what kind of testing has been done by "Gunter" on his program.
It just seems like the whole effort with Checker, rests on a cornerstone of "probably, maybe".
Probably?? Maybe?? Oh C'mon people, we can do MUCH better than that! |
|
Back to top |
|
|
| Mauricio
| Joined: 22 Mar 2006 | Posts: 21 | : | | Items |
|
Posted: Mon Apr 07, 2008 2:29 am Post subject: |
|
|
Adak wrote: | Quote: |
(We have not actually proved that we find all unavoidable sets of size up to 12, but we believe this to be true.)
|
So they haven't proved a central concept to their Checker, and then they use several other binaries, that probably haven't been really well tested, either, and then they use Gunther's program to do something else, and God only knows what kind of testing has been done by "Gunter" on his program.
It just seems like the whole effort with Checker, rests on a cornerstone of "probably, maybe".
Probably?? Maybe?? Oh C'mon people, we can do MUCH better than that! |
I think checker is a deterministic program, having all unavoidables sets is not critical for it.
In fact: Quote: | The reason why we provide all these different versions of checker is that, although using more unavoidable sets will speed things up in theory, in practice there is a performance price to pay for using more unavoidable sets, and sometimes this price is larger than the actual gain of using more unavoidable sets. |
|
|
Back to top |
|
|
| Adak
| Joined: 27 Feb 2008 | Posts: 87 | : | | Items |
|
Posted: Mon Apr 07, 2008 3:12 am Post subject: |
|
|
Oh there's a lot of intellectual babble going on, no doubt. I'm thoroughly "impressed".
Here's what's missing:
"This program (or our project) will entirely cover the full range of grids with 16 given's, to conclusively prove whether one exists, or not. If one or more valid Sudoku grids are there, they will be found."
That's what I would love to hear. How about you? : |
|
Back to top |
|
|
| coloin
| Joined: 05 May 2005 | Posts: 97 | : | | Items |
|
Posted: Mon Apr 07, 2008 10:10 am Post subject: |
|
|
You are right to question the validity of checker. But I believe it does what it says it does !
A puzzle is solved if all the unavoidables are hit......
What checker does is that it finds [in the above example] a set of 11 disjoint unavoidable sets. [no clue is the same][MCN]
A clue has to be in each one of these sets.
In this instance, searching for a 16, it takes one clue from each set and "checks" the puzzle cant be solved with 5 more clues. [This effectively is a search to cover the remaining unavoidables ]
The bigger the number of disjoint sets that can be found in the grid the quicker the program can check as there are less clues to add.
Checker is valid, it might be a bit slow for some grids [because the MCN is low], but I think the estimate is much less than for other methods.
Sudoku project
- "To this end we start with 92248 sets with 8 primary givens" - OK
- add all combinations of 8 clues
~ roughly - 10^5 * [70*7]^8 / 8!
~ 10^5 sets / ~70 clue positions / 7 options per position / 8 clues / 8 ways
~ 10^20 combinations to check [upper limit]
@ 10^5 puzzles per second that is 10^15 seconds of computing time.
Exhaustive method
- all combinations of 16 clues from a grid = 81! / [65! *16!]
~ 3*10^16
~ 1.5*10^26 for all grids
@ 10^5 puzzles per second that is 10^21 seconds of computing time.
checker might do it in 3000 million computor hours or 10^13 seconds
C |
|
Back to top |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Mon Apr 07, 2008 10:17 am Post subject: |
|
|
Adak wrote: | "This program (or our project) will entirely cover the full range of grids with 16 given's, to conclusively prove whether one exists, or not. If one or more valid Sudoku grids are there, they will be found."
That's what I would love to hear. How about you? : |
That's exactly what should be done, count me in. _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
Back to top |
|
|
| Adak
| Joined: 27 Feb 2008 | Posts: 87 | : | | Items |
|
Posted: Mon Apr 07, 2008 5:01 pm Post subject: |
|
|
I took a look into BOINC. It's quite a job to set up the server - they estimate 3 man-months, which is just WAY more than I want to spend on the administrative end of running a DC project with BOINC.
IMO we can do better just coordinating the work amongst ourselves. If we need any technical advice, we'll know just where to ask.
The core of the effort will be an exhaustive search, simple and complete. No "disjoint unavoidable sets", stuff.
Over-simplified, I see it as a three step process:
1) Generate ALL possible 16 given grids which MIGHT be what we're looking for. (That is, all the givens fit into the rule of Sudoku)
2) Split up the list into work packets, of a size that's OK to send via the internet, to our members, either via email, or to a file depot like Swoopshare, which is totally free, and will hold a large file for 30 days.
3) Run each work packet through a batch solver that can quickly tell us if the puzzle has just one solution.
Obviously, #3 is the key step, and will take the longest time. I was thinking of asking gsf if we could use his program for this, and whether, in his opinion, it would be a good choice to use.
I don't have a program to do this, and even if I added the code necessary to handle this, to my solver program, it would just not compare with the quality and speed of gsf's program. (perhaps a few others, that I'm not aware of)
I started working out some idea's into code (C) for this, but it's just a very small start so far.
Jean-Pierre, I know you've been running something geared toward this. Would you care to join in with us - show the whole world you're just as crazy as Lunatic (what a forum name!), and myself?
We do need a name for this endeavor. Quest 16, sounded good to me, what do you think?
Anyone is welcome to join in, (and *this* is your invitation to do just that), but be sure the idea of a slower, and exhaustive search through this large space, is OK with you. We're not leaving any stone unturned, in this search.
(And to think that my English teacher believed my cliche's were overdone!)
Your comments are most welcome! |
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|