Quest for THE 16 GIVEN SUDOKU

ChPicard · 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

Adak · 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! Smile

Adak

ChPicard · Posted: Sat Apr 05, 2008 11:17 pm Post subject: Who can confirm?

gsf · Posted: Sun Apr 06, 2008 1:00 am Post subject:

Adak · 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?

Razz

coloin · 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

Lunatic · 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
~~~<><~~~<><~~~<><~~~<><~~~

coloin · 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 :

Adak · 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.

Adak · 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):

Mauricio · Posted: Mon Apr 07, 2008 2:29 am Post subject:

Adak · 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". Shocked

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? : Cool

coloin · 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

Lunatic · Posted: Mon Apr 07, 2008 10:17 am Post subject:

Adak · 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. Razz

The core of the effort will be an exhaustive search, simple and complete. No "disjoint unavoidable sets", stuff. Shocked

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. Cool

(And to think that my English teacher believed my cliche's were overdone!) Very Happy

Your comments are most welcome!