SGS attack on the 16-clue search problem

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

SGS attack on the 16-clue search problem

Postby Red Ed » Tue Mar 31, 2009 10:16 am

Coming shortly to the arXiv e-prints server:

    Strong generating sets of vertex cover algebras
    H. de Vere Cole and E. Russell

    An analogue of the Schreier-Sims algorithm for strong generating sets (SGS) of permutation groups is developed for graded vertex cover algebras (GVCA). It is shown how to transform instances of certain classical cover problems into a form suitable for the SGS-GVCA algorithm, opening up the possibility of distributed attacks against previously indecomposable search spaces.
That's a rather dry abstract but it boils down to a technique which, with about 20-30 thousand hours of distributed pre-processing, will lead within minutes to a conclusive answer to the question: is there a 16-clue sudoku?

I plan to invite interested parties to join a "sudoku@home" distributed project, probably using BOINC.
Any volunteers to lend some CPU cycles:?:


fyi, here's an example of one of the "certificates" generated by the code, in this case being an SGS proving the non-existence of a 16 in grids mapping to vertex cover A1 component 2009:
Code: Select all
47596.32861385247992874356135412789678269514.......257846239715537416982291578.34
6239.1.7874.....695.....421...18.95228539471.17952684....2196....267.134816435.97
394.615.857.8423.92.8953.716.318.79282743961.1596278.4985.16.4773.59.186416278.53
83.74152.49.8523.12.1963.783.529.61768241793.....362.4764.29.5352.37.196913685.42
82.......37.....684.....7216.417.98278263914.1594286.3943.16.5726.59.314517384.96
63.94157.71.8523699.576.4215.817.93236942871.1273956.4496.17.5327.58.196851639247
27.84156.41.9523789.5763.21...19......243519.15928764....5289....831......1674.32
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby StrmCkr » Tue Mar 31, 2009 11:13 am

i'll gladly help.
i have a free 3ghz computer that does nothing.

edit: and still does nothing :P
Last edited by StrmCkr on Wed Apr 01, 2009 11:54 am, edited 2 times in total.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Postby JPF » Tue Mar 31, 2009 2:07 pm

Red Ed wrote:Any volunteers to lend some CPU cycles:?:
Yes, I am ready to help.

Red Ed wrote:fyi, here's an example of one of the "certificates" generated by the code
...
:?:
JPF
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

Postby Adak » Tue Mar 31, 2009 3:38 pm

Count me in!:)

I'm in the annual Folding@Home multi-team race "The Great Chimp Challenge", from May 5th to the 19th.

Any other dates, I'll be glad to pitch in 2 of my 3 C2D's, and the dual-quad server, 24/7.

I've been waiting for you, Red!

Edit: Very Mischievous, Edward!:D
Last edited by Adak on Wed Apr 01, 2009 4:18 am, edited 1 time in total.
Adak
 
Posts: 10
Joined: 03 March 2008

Postby coloin » Tue Mar 31, 2009 5:14 pm

Nice one Ed !

Time posted ....around 1400 GMT +0100 01/04/2009

C

:D


47596.32861385247992874356135412789678269514.......257846239715537416982291578.34
6239.1.7874.....695.....421...18.95228539471.17952684....2196....267.134816435.97
394.615.857.8423.92.8953.716.318.79282743961.1596278.4985.16.4773.59.186416278.53
83.74152.49.8523.12.1963.783.529.61768241793.....362.4764.29.5352.37.196913685.42
82.......37.....684.....7216.417.98278263914.1594286.3943.16.5726.59.314517384.96
63.94157.71.8523699.576.4215.817.93236942871.1273956.4496.17.5327.58.196851639247
27.84156.41.9523789.5763.21...19......243519.15928764....5289....831......1674.32
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby Red Ed » Wed Apr 01, 2009 9:55 am

Thank-you StrmCkr, JPF and Adak for making the effort worthwhile!:D:D:D

There were three clues that this might have been a wind-up:
  • Co-author H. de Vere Cole
  • "vertex cover A1 component 2009" (April 1st, 2009)
  • and, of course, the enormous APRIL FOOL spelled-out in empty cells of that "certificate" - clearly visible only when you stand back from the screen
I like to think of the last of those as a nod to Horace de Vere Cole's theatre prank (see link above).
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby wintder » Wed Apr 01, 2009 10:15 am

Something to know, no one cares.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby StrmCkr » Wed Apr 01, 2009 10:19 am

i see it now in colins micro text
sweet

nice:)
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Postby Red Ed » Wed Apr 01, 2009 10:38 am

wintder, you irrelevance, just crawl away won't you?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: SGS attack on the 16-clue search problem

Postby tarek » Wed Apr 01, 2009 1:30 pm

Did I fall for the
Code: Select all
47596.32861385247992874356135412789678269514.......257846239715537416982291578.34
6239.1.7874.....695.....421...18.95228539471.17952684....2196....267.134816435.97
394.615.857.8423.92.8953.716.318.79282743961.1596278.4985.16.4773.59.186416278.53
83.74152.49.8523.12.1963.783.529.61768241793.....362.4764.29.5352.37.196913685.42
82.......37.....684.....7216.417.98278263914.1594286.3943.16.5726.59.314517384.96
63.94157.71.8523699.576.4215.817.93236942871.1273956.4496.17.5327.58.196851639247
27.84156.41.9523789.5763.21...19......243519.15928764....5289....831......1674.32
joke?

yes I did:(


No thanksgiving dinner invitations for the next few years though:)

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: SGS attack on the 16-clue search problem

Postby gsf » Wed Apr 01, 2009 3:31 pm

Red Ed wrote:Strong generating sets of vertex cover algebras
H. de Vere Cole and E. Russell

its a good thing I procrastinate
else my being suckered would have been made public
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Pat » Wed Apr 01, 2009 5:11 pm

    ( off-topic )

    Procrastinate now!
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Postby wintder » Fri Apr 03, 2009 12:05 am

Red Ed wrote:wintder, you irrelevance, just crawl away won't you?


Hey, semi-irrelevant, if you please!
wintder
 
Posts: 297
Joined: 24 April 2007

Postby 999_Springs » Fri Apr 03, 2009 9:19 pm

Hmm. I have something planned for April 1st 2010...

[Edit: Actually, I might not be able to make that date. Oh well.]
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby Red Ed » Fri Apr 03, 2009 10:27 pm

We'll be watching out for you now!:D

The real joke with my spoof will be if something like it is actually possible ...
(not just a joke, but a HUGE fluke as well)
Red Ed
 
Posts: 633
Joined: 06 June 2005


Return to General