|
View previous topic :: View next topic |
Author |
Message |
| ChPicard
| Joined: 12 Mar 2008 | Posts: 82 | : | Location: Montreal, Canada | Items |
|
Posted: Wed Mar 26, 2008 2:14 pm Post subject: Open letter to all programmers |
|
|
Hello everyone
It is evident, reading this forum, that many programmers are looking for THE 16 GIVEN SUDOKU with only one solution, so I am.
The stategies are to read the Gordon's Royle list and eliminate a given, or with the same list to eliminate 2 givens and to add one digit in all the free cells.
But nobody succeeded, so we need to work together. A very long computer task, that is eliminate 3 givens and to add two digits in all free cells, everybody with the same program, the fastest one.
Who is ready to share this experience?
Jean-Pierre Sangin |
|
Back to top |
|
|
| tarek
| Joined: 31 Dec 2005 | Posts: 153 | : | Location: London, UK | Items |
|
Posted: Wed Mar 26, 2008 5:25 pm Post subject: |
|
|
Why don't we find all possible 17s first
tarek |
|
Back to top |
|
|
| Adak
| Joined: 27 Feb 2008 | Posts: 87 | : | | Items |
|
Posted: Wed Mar 26, 2008 8:37 pm Post subject: Re: Open letter to all programmers |
|
|
Jean-Pierre, do you have some proof showing that making these alterations in the 17's puzzles, will be the only way to find a unique 16 puzzle?
While intuitively it might *seem* right, I don't personally have that feeling, in this case. If you want to go exploring new territory, we shouldn't be walking in someone's footsteps, or following a premise that we're not *absolutely* confident of.
If someone has the time, this could be a nice distributed computer project. Any senior's out there looking for their project? |
|
Back to top |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Wed Mar 26, 2008 10:27 pm Post subject: Re: Open letter to all programmers |
|
|
Adak wrote: | Jean-Pierre, do you have some proof showing that making these alterations in the 17's puzzles, will be the only way to find a unique 16 puzzle?
While intuitively it might *seem* right, I don't personally have that feeling, in this case. If you want to go exploring new territory, we shouldn't be walking in someone's footsteps, or following a premise that we're not *absolutely* confident of.
If someone has the time, this could be a nice distributed computer project. Any senior's out there looking for their project? |
most if not all of the 47K sudoku17s have been through {-2+2} (2-off 2-on), some through {-3+3}
a byproduct of many 17 searches from the high end is that a 16 will appear when a
non-minimal 17 is hit (that's what my searches have been doing)
it would be nice to find all minimal 17s -- however, we don't know how many there are
and currently don't have a handle on proving that the last one found is the last one
there's already a distributed search in progress the sudoku project
they are attacking from the low end |
|
Back to top |
|
|
| Donald.Bastian
| Joined: 27 Mar 2008 | Posts: 1 | : | Location: Sydney, Australia | Items |
|
Posted: Thu Mar 27, 2008 3:22 am Post subject: |
|
|
Hi,
My name is Don. I need sudoku source code, and I may have to pay to have modifications made to that code.
I am a school teacher and I own a website which is free to teachers as a teaching resource. I plan to give teachers the ability to use the SUDOKU on my site as a reward for good behaviour and good work, in class. The Teacher would give a student a password, enabling that student a single access to the Sudoku.
Another feature would be that the students are timed on the Sudoku of the day. The fastest student for the day would have their COMPLETION TIME and NAME displayed. For eg:
CONTESTANTS TIME
1. Stinky Williams: 35:20
2. Slippery Adamas 38:15
3. Sally Flattop 41:33
I look forward to some offers.
Don Bastian,
Australia |
|
Back to top |
|
|
| Adak
| Joined: 27 Feb 2008 | Posts: 87 | : | | Items |
|
Posted: Fri Mar 28, 2008 11:09 pm Post subject: |
|
|
Attacking from the low end is right - they did the 11's in-house, and are now into the 12's with the project.
Most "teams" seem to be just one or two people, with a RAC (recent average credit) that's very low, per member.
One person asked "Why not start with the 16's?". Answer was "the search space for the 16's is quite large". That's their ultimate goal, however.
With their current computer power, by the time they get to the 16's, a group of Sudoka's could be done checking the 16's themselves, if they had some strong computers of their own.
I thought about joining in with them, but at the 12's, it's nonsense, IMO.
And Don, your topic deserves a thread of it's own. I doubt it will be seen buried in a thread of a very different topic. |
|
Back to top |
|
|
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Sat Mar 29, 2008 4:54 pm Post subject: |
|
|
FWIW, my modest opinion.
The number of 17s has increased dramatically in the last few months. I would take every one of them and delete one clue/given at a time and note how many solutions result for each 16. Once I had a collected the number of solutions for all possible 16s created from the known 17s, I would then examine the 16s with the largest number of solutions to see why adding a specific clue leads to a single solution.
This may lead to a better understanding in the quest for a 16 with a single solution.
A lot of W-O-R-K!!! |
|
Back to top |
|
|
| ChPicard
| Joined: 12 Mar 2008 | Posts: 82 | : | Location: Montreal, Canada | Items |
|
Posted: Sun Mar 30, 2008 10:10 am Post subject: |
|
|
daj95376 wrote: | examine the 16s with the largest number of solutions to see why adding a specific clue leads to a single solution.
This may lead to a better understanding in the quest for a 16 with a single solution.
A lot of W-O-R-K!!! |
Yes for me it is a good idea
and it is why my computers are working all the day long
(I am working for the Guinness book of records )
Does anybody got an idea working
with the total number of candidates
at each time we fix a new clue in the grid? |
|
Back to top |
|
|
| coloin
| Joined: 05 May 2005 | Posts: 97 | : | | Items |
|
Posted: Wed Apr 02, 2008 1:50 pm Post subject: |
|
|
Adak wrote: | I thought about joining in with them, but at the 12's, it's nonsense, IMO. |
I agree, working up through 12,13,14,15,is fairly silly !
I am not alone in thinking that it is very unlikely that there is a 16. A 16, if there is was one, should have a high density of 17s near it, and therefore we would be very very likely to find it.
The 17s that gsf is finding now are remote in the sense that each 17 has much fewer 18s near it. The chances are slim that a 16-puzzle exists - without a 17 and only a few 18-puzzles near it.
daj95376 wrote: | I would then examine the 16s with the largest number of grid solutions to see why adding a specific clue leads to a single solution. |
The biggest megaclue was found with over 11 million grid solutions for a single clue. Red Ed/gsf
try removing r8c4 from this ...
Code: | .1.|5..|...
...|.7.|.8.
...|...|..9
---+---+---
7..|.2.|4..
2..|...|5.1
...|...|...
---+---+---
6.2|...|.4.
...|1..|3..
...|9..|... | ........ you get 11339281 grid solutions !
I think the fact there is 17-clue puzzles is down to the sheer numbers of grids [~ 5*10^9] and the number of minimal puzzles per grid [~10^15].
Almost all solution grids will have a 19-clue puzzle within them. In these puzzles all the many unavoidable sets have at least one clue. It just so happens that there are 17-clue puzzles in some grids - where all the unavoidable sets can be hit with 17 clues. The fact that this happens is related to the large puzzle space and the small but finite probability of this occurring.
I think the sudoku team needs to take more advice before embarking on the 12-15 exercise.
I proposed a classification system of 17-puzzles here, which gets rid of many of the isomorph issues Here
based on the fact that every puzzle has these 5 [6,7,8,or 9]equivalent [?non-adjacent]clues Code: | 1..|...|...
...|*..|...
...|...|*..
---+---+---
.*.|...|...
...|.5.|...
...|...|.6.
---+---+---
..*|...|...
...|..8|...
...|...|..9 |
gsf wrote: | it would be nice to find all minimal 17s -- however, we don't know how many there are and currently don't have a handle on proving that the last one found is the last one |
It might be that it can be used to prove that we have eventually found all the 17-puzzles [when and if we do]
C |
|
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
|