|
View previous topic :: View next topic |
Author |
Message |
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Fri Nov 25, 2005 5:31 pm Post subject: |
|
|
Quote: |
Could this fact have anything to do with how they were generated
|
Honestly, I don't know, but I don't see any reason why it would be the case that there is any bias. Maybe that XY wings and other complex patterns are just very special cases of 1-look-ahead rules
and there is no special reason (especially with larger grids) that they appear in machine generated puzzles. |
|
Back to top |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Fri Nov 25, 2005 8:30 pm Post subject: |
|
|
Three more:
Code: |
....L.1.8H.CO..P....FA...
P1.2.4CO...K..A..3H8...7.
I..H.G.5.B.6.M..A24.K..9.
....6I.KF9..5.P.J1.BDCE.M
.A....2...F..L..E.M.6.5O3
7..1.C...8.L9..4P.5.G.K..
JO.5H.M2.I.7.F.6D..A4..NE
E.3.NO....K2...LG..7JM...
.9F.CJ.H....A.NKB.1..2.5.
2LB...5..7.P36H.M..N...1D
.....P..B....46.HJ.......
B4..7LI.C.GD2...KA.3H....
K5......6J1.........27O8P
LP...5K.G..JB3.......1.M.
..EG...4.F.NKC...O..9.B..
..MI...D32AGP..5O...74.BN
FC74.....1..LO..8...5.D.J
..JN....H...E.I...DPA3.6.
AE.......O3F..5.........H
...8..6......24.9G....I.1
.M....8.9..O1.F.C.EL3...A
.N...E.3.....I7M1...ODG.K
1......P.N9..D..5........
.I.P..FGOCMA.......J.5..2
.GK....7...3.....92..B.L4
...H....GKM.43..B.D......
15I.C....8B.6D.7G....A.H4
.7...F..B...J.E16.N....3.
...D.1...6L7.H.5K....P98F
KJ.AF.5CHO...NP2M.....B..
4..K..I9.M.DNP..A.3..E5O6
PGC...HE.....I5..M...7..J
.B.EJ..G.5..L....D.48.2..
.D....N.4.J.2A..H..5..F1.
8....AJLD.7..OM...1B....P
CH...N..7.........B3.....
I..O.JL..P5...3......KH.8
D.259.E......6.......L3..
...3K6.B.AE..74N25H..G1..
.L.B..41.HC...G.OIP8..MN7
.........2.C.4.L....69.I5
N...7.C...69.5.A......PKL
....L.G...13.BOMP.82..D7H
...C.H..5.P.E.K...I7.....
JO..P.96ABI8.....C..N..4G
.NA8H.32..O4..IB..L9G..J.
..4.GD..M.3..27INJ.O.....
.C9L..A..J.....6.2..I..F.
BK...4..F.A.CL..87.1.O.M.
6..P.I.5...M..N....F....D
..6F.....5..3.....H..A.M2
.....3....I8.A.MC.KJ.LNG.
.I.7N..K.2..6...3D..B.O85
.3A.PF.D8OBK7.2....L6.9H4
.K..CBML.....O.A8.G4.D...
1.4.AGL..M5..F.O.9....P2.
..I.........8......N4E...
J.C8.1.6.3.LO.K7AG2P9.H..
.2.3BH..9.A...G......O..L
.H..M8.J.....NI1.LEF....B
I5..4.....G.27..K..3.M..H
P..E..I.A..3B.8....G.2...
AJ......NFK.I.O9476..G.1.
.976...E3H....M5.F......O
.F.M3.5.GKC4.HJ.N.....ID7
..L1K..9.J37.ID..B..E6...
.82OH.1..PNML...E..C...J.
....JLFN.B..G..6M..H..D.9
...C.A...I.6.......K.5...
E.G.I.....O....J.8F......
..M4..9.D.7.K.FE.3O......
H.N.....14E..B3L..8I...AG
K.O.62.PM...N..H...18C.9.
LC..8.3...2...H.G...J..4E
.B..9NK.E....C6.P.4D.71OI
|
I'll put the next ones on my website. |
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Sat Nov 26, 2005 5:11 am Post subject: |
|
|
Kranser, could you try 16*16s first and report whether you find any
xy-wings there ?
See e.g.
http://magictour.free.fr/top44
could be that they just become rarer and rarer as the size increases
and the 10 puzzles from frisch are maybe not enough
here's some statistics for 9*9s from Nick70:
singles 15198 46,15%
box-line exclusion 10461 31,77%
hidden pair 2384 7,24%
turbot 1899 5,77%
xy-chain 1572 4,77%
forcing chain 1121 3,40%
multi forcing chain 129 0,39%
naked pair 100 0,30%
naked triplet 23 0,07%
hidden triplet 14 0,04%
forcing tree 12 0,04%
x-wing 11 0,03%
swordfish 4 0,01%
jellyfish 2 0,01% |
|
Back to top |
|
|
| xyzzy
| Joined: 24 Aug 2005 | Posts: 80 | : | | Items |
|
Posted: Mon Nov 28, 2005 12:41 pm Post subject: |
|
|
dukuso wrote: |
SATZ: 42 and 122 Gcycles (P4-2.6GHz)
xyzzy: 10 and 356 Gcycles (P2-400MHz)
frisch: 7.33 and 63 Gcycles (P4-2.8GHz)
dukuso:231 and 2197 Gcycles (P4-2.6GHz)
hmm, why is it so much ? Are you sure your numbers are correct ?
|
I'm sure the numbers are correct. It looks like you are trying to find all solutions, instead of just one? That is much slower of course. I don't think it's nearly as interesting of a problem either. QCP is NP-complete, so the only improvement possible lies in heuristic methods to find a solution on average faster. If you look at SAT, everything besides the basic Davis-Putnam method from 1960 is nearly useless if you change the problem from testing for satisfiability to finding all solutions. |
|
Back to top |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Mon Nov 28, 2005 1:17 pm Post subject: |
|
|
Well, even if the problem is NP-complete, we can try to optimize algorithms by choosing branching choices in a clever way. We can get efficient algorithms for a large class of instances (the theoretical worse-case compelexity does not force average difficulty to be high).
I uploaded a new version of my solver, together with 16 minimal 25x25 sudokus here:
http://www.eleves.ens.fr/home/frisch/sudoku.html
-- Alain |
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Mon Nov 28, 2005 3:34 pm Post subject: |
|
|
> dukuso wrote:
>
> SATZ: 42 and 122 Gcycles (P4-2.6GHz)
> xyzzy: 10 and 356 Gcycles (P2-400MHz)
> frisch: 7.33 and 63 Gcycles (P4-2.8GHz)
> dukuso:231 and 2197 Gcycles (P4-2.6GHz)
>
> hmm, why is it so much ? Are you sure your numbers are
> correct ?
>
>
> I'm sure the numbers are correct.
> It looks like you are trying
> to find all solutions,instead of just one?
there is only one. Verifying this takes about twice as much time
as when you stop as soon as the solution is found.
> That is much
> slower of course. I don't think it's nearly as interesting of
> a problem either.
I think it's almost the same as 2 find-solution-only-puzzles.
> QCP is NP-complete, so the only improvement
> possible lies in heuristic methods to find a solution on
> average faster.
no, the improvement also comes from better pruning of the searchspace
> If you look at SAT, everything besides the
> basic Davis-Putnam method from 1960 is nearly useless if you
> change the problem from testing for satisfiability to finding
> all solutions.
but these are unique-solution puzzles. Once you found the solution
you can exclude it to get another -now final- SAT-problem.
It's astonishing how some puzzles are so difficult and others so easy.
Also, why the same puzzle is sometimes solved quickly
and then takes much longer. I'd like to understand this
behaviour.
-Guenter |
|
Back to top |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Tue Nov 29, 2005 6:14 pm Post subject: |
|
|
dukuso wrote: | Code: | http://magictour.free.fr/qwhm25 |
|
here are my timing/guesses/puzzle# 2.8Ghz p4:
Code: |
2.621602 594 1
0.960853 230 2
1.038843 244 3
11.419264 3178 4
4.984242 1172 5
38.855093 9226 6
2.084683 634 7
0.926859 192 8
7.482863 2034 9
0.417936 98 10
0.822875 223 11
0.591910 112 12
4.795271 1211 13
1.881714 470 14
19.945968 5706 15
0.048993 14 16
0.044993 5 17
13.855893 3600 18
0.395940 108 19
5.826114 1551 20
0.870868 220 21
0.470928 111 22
1.673746 461 23
0.939857 246 24
7.663835 2102 25
1.190819 351 26
1.403787 416 27
1.709740 379 28
0.349946 63 29
0.045993 5 30
0.807878 208 31
0.716891 212 32
3.301497 896 33
3.904407 920 34
0.916860 208 35
0.401939 86 36
1.727738 410 37
0.069989 16 38
0.293955 61 39
1.009847 281 40
4.623297 1282 41
2.122677 544 42
1.637751 322 43
1.640751 380 44
5.060231 1131 45
1.164823 275 46
0.075988 7 47
0.586911 130 48
0.181972 29 49
1.796727 468 50
0/s puzzles 50 seconds 167.365556 nodes 42822
|
|
|
Back to top |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Tue Nov 29, 2005 6:17 pm Post subject: |
|
|
my timings on 2.8Ghz p4:
Code: |
5.403179 716 1
12.971028 2575 2
0.411937 78 3
1.210816 286 4
0.749886 168 5
0.165975 28 6
1.086835 194 7
1.296802 206 8
0.355946 63 9
0.164975 23 10
0.613907 115 11
1.688743 257 12
0.323951 58 13
0.310953 45 14
0.621905 139 15
0.345948 53 16
0.207968 19 17
0.078988 11 18
1.243811 215 19
0.949855 242 20
3.092530 699 21
0.084987 6 22
0.630904 71 23
0.217967 39 24
0.633904 99 25
0.202969 34 26
0.099985 15 27
0.321951 52 28
0.148977 25 29
0.979851 140 30
3.480471 616 31
0.182973 21 32
0.371944 68 33
0.138979 12 34
0.122981 18 35
1.320799 293 36
5.550156 946 37
0.112983 19 38
0.315952 46 39
1.020845 214 40
1.216815 246 41
2.087682 402 42
1.235812 256 43
0.522921 86 44
0.424935 84 45
0.731889 174 46
0.487926 69 47
0.811876 107 48
3.079532 415 49
0.291956 44 50
1/s puzzles 50 seconds 60.128859 nodes 10807
|
|
|
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: Wed Nov 30, 2005 5:32 am Post subject: |
|
|
yes, they took me 20350sec. with 2.6GHz, until solution found,
same program as "guenter2" in the 16*16 thread, but maybe I could
adapt some parameters for 25*25.
SATZOO was able to solve these 16 in 2242sec.
I also figured out now, why my SAT-encodings were
still ineffective, so all the timings for SATZ,SATZOO need
to be revised. Expecting 10-20 times faster for SATZ,3 times
faster
for SATZOO |
|
Back to top |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Wed Nov 30, 2005 7:12 pm Post subject: |
|
|
thanks, 2.8Ghz p4
Code: |
505.450160 52747 1
13.346971 1473 2
0.992849 69 3
5.906102 488 4
2.797575 287 5
179.300743 20151 6
63.053414 6523 7
1.717739 141 8
5.666138 571 9
61.436661 5312 10
261.788201 28449 11
785.010661 82303 12
16.834440 1722 13
15.259681 1519 14
320.185324 31539 15
368.852926 39967 16
0/s/GHz GC 7301.3 C/n 26719067 puzzles 16 seconds 2607.599585 nodes 273261
|
|
|
Back to top |
|
|
| xyzzy
| Joined: 24 Aug 2005 | Posts: 80 | : | | Items |
|
Posted: Wed Nov 30, 2005 9:53 pm Post subject: |
|
|
dukuso wrote: |
yes, they took me 20350sec. with 2.6GHz, until solution found,
|
Benchmarking these problems on a P2-400 is really trying my patience.... I've been working on the first of the minimal order 25 problems for an hour, I think it'll take me a week to solve all 16.
Quote: |
SATZOO was able to solve these 16 in 2242sec.
I also figured out now, why my SAT-encodings were
still ineffective, so all the timings for SATZ,SATZOO need
to be revised. Expecting 10-20 times faster for SATZ,3 times
faster
|
I read about the 3D SAT encoding of QCP in that paper you posted earlier, and it sounded very simple. I'm not sure why you said it needed lots of memory. Are you somehow reducing the SAT problem before giving it to the SAT solver?
As I understand for a size N latin square, you have N^2 boolean variables in the SAT problem. There are 3*N^2 'At-Least-One' terms, which have N variables each, plus 3*N^2 'At-Most-One' sequences, where each AMO sequence has N^2-N terms with two variables per term. These terms are the same for any latin square of size N. Then for each given value in the latin square, there is one singleton term for that value. These terms are the only ones that change.
Of course this SAT problem can be reduced to a much simpler one. If there is only one solution, it can be turned into a one term problem with just N variables. But performing this reductions is the whole point of the SAT solver, it would be like saying SATZ is really fast when you give it an already solved problem. |
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Thu Dec 01, 2005 2:37 am Post subject: |
|
|
yes, I did take the 3D-encoding as desribed in the Spanish paper,
(see link above)
but you can reduce the .cnf a lot, by eliminating the variables
corresponding to the givens. And this is, what lsencode does
(Gomes' program to convert QWHs to .cnfs , available
from Gomes' webpage)
and they were using this encoding in the paper
(but didn't tell us...)
With SATZ I'm getting 9sec (1GHz). now for a random QWH of order 35
with 396 holes vs. 109sec before.
The Spanish paper gives 6sec.
I had assumed, SATZ were somehow doing this reduction by itself,
but apparantly this is not very efficient.
SATZOO is better in doing this, bút it's still faster
to feed it directly with the reduced form.
I also reduce the exact-cover-matrix now before
giving it to my solver for 3-fold (or such) speed-improvement
I changed my program at
http://magictour.free.fr/sud2sat.exe
accordingly.
-Guenter |
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Thu Dec 01, 2005 5:04 am Post subject: |
|
|
xyzzy wrote: | dukuso wrote: |
yes, they took me 20350sec. with 2.6GHz, until solution found,
|
Benchmarking these problems on a P2-400 is really trying my patience.... I've been working on the first of the minimal order 25 problems for an hour, I think it'll take me a week to solve all 16.
## you can pick the easy ones. e.g. Nr. 2,3,4,5
Quote: |
SATZOO was able to solve these 16 in 2242sec.
I also figured out now, why my SAT-encodings were
still ineffective, so all the timings for SATZ,SATZOO need
to be revised. Expecting 10-20 times faster for SATZ,3 times
faster
|
I read about the 3D SAT encoding of QCP in that paper you posted earlier, and it sounded very simple. I'm not sure why you said it needed lots of memory. Are you somehow reducing the SAT problem before giving it to the SAT solver?
## see my post above. I had .cnf files with 40MB for 35*35 QWHs
As I understand for a size N latin square, you have N^2 boolean
## n^3 variables. One per row,column,symbol
variables in the SAT problem. There are 3*N^2 'At-Least-One' terms, which have N variables each, plus 3*N^2 'At-Most-One' sequences, where each AMO sequence has N^2-N terms with two variables per term. These terms are the same for any latin square of size N. Then for each given value in the latin square, there is one singleton term for that value. These terms are the only ones that change.
## 3*n*n clauses of length n
## 3*n*n*n*(n-1)/2 clauses of length 2
## one clause of length 1 for each clue
Of course this SAT problem can be reduced to a much simpler one. If there is only one solution, it can be turned into a one term problem with just N variables. But performing this reductions is the whole point of the SAT solver, it would be like saying SATZ is really fast when you give it an already solved problem. |
just the variables with the forbidden placements
(forced by the clues) can be deleted and the corresponding
clauses updated. And then the variables are renumbered |
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Thu Dec 01, 2005 6:34 am Post subject: |
|
|
finally the discussion is going into the direction, I was hoping
for since long, but nobody really cared about 16*16 or larger ...
with the new, short encoding for the SAT-solvers I get these
Code: |
average timings for the 16 minimal 25*25 sudokus from Alain's webpage with 2.6GHz :
correlations expect. deviation
------------------------------------------------------------------
99 28 79 53 50 69 140.143 163.039 SATZOO (long encoding)
28 99 50 42 9 45 1271.85 2492.642 Guenter (sudqwh.c3)
79 50 99 45 82 92 175.511 239.981 gsf(01.dec.2005)
53 42 45 99 33 58 72.033 101.521 satz215
50 9 82 33 99 86 92.375 149.899 SATZOO (short encoding)
69 45 92 58 86 99 568.885 667.376 Alain
------------------------------------------------------------------
|
SATZ improves a lot on short,reduced encodings , while for SATZOO
it doesn't matter a lot. This suggests, that SAT could be improved
be regularly reducing the cnf by the assigned variables
what do you think, are sudokus better benchmarks for SAT-solvers
than QWHs ? Or at least an interesting supplement to these ?
I'm not yet sure about the phase transition for sudokus,
it could be like 2*n^1.65 vs. 1.7*n^1.55 for QWHs.
Clearly sudokus are harder for same n.
Last edited by dukuso on Thu Dec 01, 2005 8:50 am; edited 2 times in total |
|
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
|