Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Open letter to all programmers

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Wed Mar 26, 2008 2:14 pm    Post subject: Open letter to all programmers Reply with quote

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
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Wed Mar 26, 2008 5:25 pm    Post subject: Reply with quote

Why don't we find all possible 17s first Question Shocked

tarek
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Wed Mar 26, 2008 8:37 pm    Post subject: Re: Open letter to all programmers Reply with quote

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
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Wed Mar 26, 2008 10:27 pm    Post subject: Re: Open letter to all programmers Reply with quote

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
View user's profile Send private message Visit poster's website
Donald.Bastian

Joined: 27 Mar 2008
Posts: 1
:
Location: Sydney, Australia

Items
PostPosted: Thu Mar 27, 2008 3:22 am    Post subject: Reply with quote

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
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Fri Mar 28, 2008 11:09 pm    Post subject: Reply with quote

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. Very Happy

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
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sat Mar 29, 2008 4:54 pm    Post subject: Reply with quote

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
View user's profile Send private message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Sun Mar 30, 2008 10:10 am    Post subject: Reply with quote

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 Laughing Laughing Laughing )

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
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Wed Apr 02, 2008 1:50 pm    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron