View previous topic :: View next topic |
Author |
Message |
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Mon Aug 01, 2005 7:51 am Post subject: and now the 25*25 |
|
|
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 |
|
|
| droid42
| Joined: 29 Jul 2005 | Posts: 20 | : | | Items |
|
Posted: Wed Aug 03, 2005 10:26 am Post subject: |
|
|
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 |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Wed Aug 03, 2005 10:56 am Post subject: |
|
|
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 |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Wed Aug 03, 2005 1:46 pm Post subject: |
|
|
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 |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Fri Aug 05, 2005 5:14 pm Post subject: |
|
|
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 |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Wed Nov 16, 2005 3:41 pm Post subject: My OCaml solver |
|
|
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 |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Wed Nov 16, 2005 3:45 pm Post subject: |
|
|
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 |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Wed Nov 16, 2005 4:00 pm Post subject: |
|
|
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 |
|
Back to top |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Thu Nov 17, 2005 5:07 am Post subject: the next one |
|
|
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 |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Thu Nov 17, 2005 5:48 am Post subject: |
|
|
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 |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Thu Nov 17, 2005 6:09 am Post subject: |
|
|
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 |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Thu Nov 17, 2005 6:10 am Post subject: |
|
|
20 minutes to prove there is a single solution... |
|
Back to top |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Thu Nov 17, 2005 6:13 am Post subject: |
|
|
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 |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Thu Nov 17, 2005 9:12 am Post subject: |
|
|
Down to 7 minutes total with a few implementation tricks + a new heuristics to pick the next cell... |
|
Back to top |
|
|
|