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   

and now the 25*25
Goto page 1, 2, 3, 4, 5  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles
View previous topic :: View next topic  
Author Message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Mon Aug 01, 2005 7:51 am    Post subject: and now the 25*25 Reply with quote

this size could be already too big, even for computer-solvers !

Assume you take a random sudoku-grid of size 25*25 and
then delete about 60% of the entries at random.
It seems almost impossible to determine if there is
a unique solution to that sudoku.

Here is a 25*25 generated almost randomly, I don't know how
many clues can be removed so that there is still a unique
solution. And I can't solve it with my solver in reasonable time.
I'm curious, whether anyone can solve it !





Code:


+-----+-----+-----+-----+-----+
|.O.L.|..F.V|H....|...G.|.....|
|...Y.|AT...|L....|..MV.|...JS|
|.B..I|.W...|TK.D.|CU.AQ|L...F|
|U....|DJ.M.|N...Q|.I.BW|.O..V|
|.E.QJ|LB...|.IXV.|.S...|WA..K|
+-----+-----+-----+-----+-----+
|EJTUO|M....|Q..W.|L...N|D...Y|
|X....|.H.B.|JY..F|EV.U.|..L..|
|F....|...R.|....S|.KC..|OJW..|
|.W.M.|...IU|.R.GV|.DO..|FTKE.|
|G.DRV|.PK.N|O..C.|FAT..|.U.H.|
+-----+-----+-----+-----+-----+
|.U.K.|Q.O..|.J.ML|S....|.VNT.|
|OI..F|.LTCM|.D..E|.G...|..R.J|
|P..NL|....J|GX..Y|....T|.EM.O|
|M..S.|GV...|W.AQC|..KNE|..H..|
|....Q|...W.|.TV..|..Y.J|ULP.G|
+-----+-----+-----+-----+-----+
|..M.N|RI..W|.ET..|B..KD|..OYA|
|.T.PC|Y..H.|K...D|.E...|.R.W.|
|Y..X.|P..N.|I.U..|TJWM.|HF..D|
|.KVA.|CO...|.Q.P.|.....|E....|
|RS.O.|.U..G|A..LX|Q...H|I....|
+-----+-----+-----+-----+-----+
|..XFE|..P.A|.UWIR|...H.|SYD..|
|J.GHS|..W.R|.....|D..EV|....P|
|B....|O..FH|YM...|PTGS.|...NW|
|KCP..|NX.E.|....G|...R.|.BTV.|
|....R|V....|EAQ..|UWBY.|KG.MH|
+-----+-----+-----+-----+-----+
Back to top
View user's profile Send private message Send e-mail Visit poster's website
droid42

Joined: 29 Jul 2005
Posts: 20
:

Items
PostPosted: Wed Aug 03, 2005 10:26 am    Post subject: Reply with quote

My solver manages to fill in 55 numbers in about 600ms before running out of options.

Interesting to note it found a solitary setptuple on column 6 and a 14-tuple (!!!) on row 19 (which led to 2 valid reductions). Not convinced a human would ever be able to spot that.

Super-colouring had a good run too (10 seconds to analyse the whole grid), but even after 672 million tests to discover 1241 cross-cell implications, there were no further reductions to be found.

Here's how far it got:

Code:

. O . L M . . F . V H . . . . . . . G . . . . . E
. . . Y . A T . . . L . . . . . . M V . . H . J S
V B . G I . W . . . T K . D J C U E A Q L M . . F
U . . . . D J . M . N . . . Q . I L B W . O . . V
. E . Q J L B . . . . I X V . . S . T . W A . . K
E J T U O M . . . . Q . K W . L . . . N D . V . Y
X . . . . W H . B O J Y . T F E V . U . . . L . R
F . . . . . . V R . U . . . S . K C . . O J W . .
. W . M . . . . I U . R . G V . D O J . F T K E .
G . D R V . P K . N O . . C . F A T W . . U . H .
. U . K G Q . O . . . J . M L S . . . . . V N T .
O I . . F . L T C M . D . . E . G . . U . W R . J
P . . N L . . . . J G X . U Y W . . . T . E M . O
M . J S T G V . . . W . A Q C . L K N E . . H . .
. . . E Q . . . W . . T V . . . . Y . J U L P . G
. . M J N R I . . W . E T . H B . U K D . . O Y A
I T U P C Y . . H . K . . . D . E . . . . R . W .
Y . . X B P . . N . I V U . O T J W M . H F . . D
. K V A . C O . . . . Q . P N . . . . . E . . . .
R S . O D . U . . G A W . L X Q . . . H I K . . .
. . X F E B . P . A V U W I R . . . H . S Y D . .
J . G H S . . W . R . . . . T D . . E V . . A . P
B . . . . O . . F H Y M . . K P T G S . R . E N W
K C P W . N X . E . D . . . G . . . R . J B T V .
. . O . R V . . . . E A Q . P U W B Y . K G F M H
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Wed Aug 03, 2005 10:56 am    Post subject: Reply with quote

very interesting !
Do you think the current set of "rules" can be extended such that these puzzles become feasable or are we just at the P=NP- border ?

The proof that sudokus are NP-complete only spots
a small n*n latin square in a special sudokugrid
and doesn't consider the rest of the n*n * n*n grid.
But I feel, that completing sudokus of size n*n * n*n is not
so much easier than completing latin squares of size n*n * n*n !
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Wed Aug 03, 2005 1:46 pm    Post subject: Reply with quote

I tried again to solve giving it more time - and now I succeeded.
But the reason for this could be the way how the puzzle was generated:

(1) start with an empty grid
(2) fill in a random clue
(3) solve
(4) if there is no solution or if it takes too long, then remove that clue
and go to (2)
(5) if there are more than one solution go to (2)
(6) remove a random clue
(7) if there is more than one solution or if it takes too long
then put that clue in again and go to (6)
(8) goto (6)


at some point I interrupted at (8) and did a random transformation
of the puzzle (permuting rows,columns, etc.) .

Then my solver couldn't solve in in some minutes.
But apparantly it could in some more minutes ;-)


Guenter.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Fri Aug 05, 2005 5:14 pm    Post subject: Reply with quote

after reading some papers about latin squares completion,
I no longer think that a random 25*25 sudoku
would already be a problem for a good solver.
They can complete latin squares of orders 40*40 !
See the "papers and links" from the math-forum
Back to top
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Wed Nov 16, 2005 3:41 pm    Post subject: My OCaml solver Reply with quote

Hello,

I just started to implement my own solver in Objective Caml. It can solve the 25x25
puzzle above in 2.62s (to find the solution, 10.49s total to check unicity).


Alain
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Wed Nov 16, 2005 3:45 pm    Post subject: Reply with quote

OK, I see you need a harder one.
Try this:

Code:


...E5 .4..F D..B. .KMG. ...1.
7.... O..2. ..G.L 1.C64 ..B3.
1P... ..... I...K ...O. .DN2.
DK.M. ...J. 1H... L..I2 9G.EO
H.L.. .G.B6 8.7F. 95... ....4

6FH.9 5.... .4... .G... .81..
...8. ..2.. N...1 6.LM5 .4..9
P4I.. ..D6B JK98. ...CN M...2
NO3.. 4F1I. PB... .E.8. J....
...B7 NE.C. LGFH6 ..J2. .OK.A

..932 .MO7. .1... B..4F .....
...D4 ..... ..K.. .C3.. .A9PM
.6... .AE.4 5...D ..K.. H.C..
M.7KO ..F.. 2PH.A ....6 ...B.
.H..P L.... .I3.9 GM.N. O.F4.

..K.. 7..4. E..D. P.NA. .B89G
F.... .P.AI .92.. OD4.J 3K657
.2... ..L.M F.P.. .91.H A...J
O...A 3.KN. ...5J E.... ....H
.3.JM F18.D ..AKH .6.B. E.I.L

..E.. 2...5 ...G. ...P. K1L..
...C. ..GE. .F.J. H.5.. .....
..M.K J6I8. AO.L. C.BF. .5...
B5... .7..9 ..8.P 2L... .FO.I
...P. ....O 47I.. J.... 2C...


Back to top
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Wed Nov 16, 2005 4:00 pm    Post subject: Reply with quote

Thanks a lot ! Indeed, this one is much more difficult. My solver takes 28s to find a solution, and 140s total to prove unicity...

-- Alain, waiting for the next one Smile
Back to top
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Wed Nov 16, 2005 5:15 pm    Post subject: Reply with quote

Btw, I made the solver publicly available here:

http://www.eleves.ens.fr/home/frisch/sudoku.html

-- Alain
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Thu Nov 17, 2005 5:07 am    Post subject: the next one Reply with quote

this one took me 10 hours to create and prove it's minimal !
see
http://magictour.free.fr/min25
for a more computer-readable format



Code:



+-----+-----+-----+-----+-----+
|.1.KA|..B.D|P42N.|...7G|..E6.|
|...8.|..NIO|...6G|..5HF|.C..A|
|.6...|3....|...J.|4K..B|H.P.D|
|CO4D.|.9AKE|...I.|.J126|35...|
|.B57.|H68..|.9.OK|.C..N|4.2F.|
+-----+-----+-----+-----+-----+
|.I.1.|.....|..J..|7.C8D|A3...|
|...32|..7M.|.E...|....4|FB.91|
|6..4.|...2.|3.P1.|AO...|..5.7|
|...F.|E.I84|6B97O|.5...|.PLH.|
|8.B..|AN...|..L..|..G9.|.M6K.|
+-----+-----+-----+-----+-----+
|BM.L3|.C.5.|....E|..O.K|67...|
|...2.|1.K..|9..5.|.....|G..A.|
|.A...|.H...|..4.L|16IN.|..D3.|
|.K...|..4..|BD.P.|G....|ENF..|
|GE75.|....P|K3..C|J...A|..M2L|
+-----+-----+-----+-----+-----+
|...94|CJ.B.|..7.F|M..P8|I...E|
|5..OI|PK...|.1E.6|94N..|M.B..|
|D.A.6|..2..|..N..|..EO.|C4K.F|
|.CP.7|.46..|I58..|H...J|.1A.O|
|.2...|9.GE7|.C.AP|I....|.D...|
+-----+-----+-----+-----+-----+
|1..I.|.B5H.|O.K2.|.....|.EN..|
|....P|O....|C6.GI|.N3..|8....|
|....5|.A..G|8...1|K.PB.|J...H|
|...MK|8I.N.|A...4|.7J61|...5G|
|2....|...16|D....|LMH..|7A3OK|
+-----+-----+-----+-----+-----+


Back to top
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Thu Nov 17, 2005 5:48 am    Post subject: Reply with quote

I had an embarassing bug in my solver (some heuristics was applied only to the first line...).

With the fixed solver, I could find a solution to this problem in 22.50s. Still waiting for the other solutions after several minutes:

Here it the solution:

H1IKA5FBCDP42N3O8M7GLJE69
MP98J42NIOE7D6G3L5HFKC1BA
L62NF37MG15ACJ84K9EBHOPID
CO4DGL9AKEHFBIMPJ1263578N
3B57EH68PJL91OKDCAIN4G2FM
PIL1965HOBNKJM27FC8DA3GE4
O5N32DP7MLGEACH6IKJ4FB891
6JE4MKG92F38P1DAOBLHNI5C7
AGKFCE3I846B97ON521MDPLHJ
87BHDAN1JCFIL45E3G9POM6K2
BMDL3NCJ5A12GHE8POFK6794I
4FC2H1DKLI9N65JBE7M3G8OAP
9AJPOGHEF27M48L16IN5BKD3C
IK8617M493BDOPAGHLC2ENFJ5
GE75NB8O6PK3IFCJ94DA1HM2L
N3194CJLB52O7KFMADP8I6HGE
5LGOIPKFAHJ1ED694N3CM2B78
DHAJ6I1238MGNL95BEO7C4KPF
KCPE7M46DNI583BH2FGJ91ALO
F2MB89OGE74CHAPI16KL5DJN3
143ILFB5HMOJK27CG8A9PEND6
J9HAPOLD7KC6MGI2N35E8F41B
7N6C52A34G8LFE1KDPBOJ9IMH
EDOMK8IPN9AH3B4F7J612LC5G
28FGBJEC16DP59NLMH4I7A3OK
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Thu Nov 17, 2005 6:09 am    Post subject: Reply with quote

I notice that you find the solutions pretty quickly while the
whole search takes considerably longer.
So, maybe your solver is better suited as a heuristic
or incomplete solver ?
Or is this common behaviour of any solver ?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Thu Nov 17, 2005 6:10 am    Post subject: Reply with quote

20 minutes to prove there is a single solution...
Back to top
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Thu Nov 17, 2005 6:13 am    Post subject: Reply with quote

There is some heuristics in the solver to choose a on which to branch, but the digits are then tried in turn. So it's maybe simple that solver is lucky: the puzzle generator put small digits in difficult cells (?). I guess that a random permutation on digits would break this luck.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Thu Nov 17, 2005 9:12 am    Post subject: Reply with quote

Down to 7 minutes total with a few implementation tricks + a new heuristics to pick the next cell...
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles All times are GMT
Goto page 1, 2, 3, 4, 5  Next
Page 1 of 5

 
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