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 Previous  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
frisch

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

Items
PostPosted: Fri Nov 25, 2005 5:31 pm    Post subject: Reply with quote

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
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: Fri Nov 25, 2005 8:30 pm    Post subject: Reply with quote

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
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: Sat Nov 26, 2005 5:11 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
xyzzy

Joined: 24 Aug 2005
Posts: 80
:

Items
PostPosted: Mon Nov 28, 2005 12:41 pm    Post subject: Reply with quote

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

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

Items
PostPosted: Mon Nov 28, 2005 1:17 pm    Post subject: Reply with quote

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
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: Mon Nov 28, 2005 3:34 pm    Post subject: Reply with quote

> 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
View user's profile Send private message Send e-mail Visit poster's website
gsf

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

Items
PostPosted: Tue Nov 29, 2005 6:14 pm    Post subject: Reply with quote

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

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

Items
PostPosted: Tue Nov 29, 2005 6:17 pm    Post subject: Reply with quote

dukuso wrote:

http://magictour.free.fr/sudoku.25n

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

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

Items
PostPosted: Tue Nov 29, 2005 6:30 pm    Post subject: Reply with quote

Can you run your solver on the minimal puzzles from here:

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

?


These should be much more difficult.
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 30, 2005 5:32 am    Post subject: Reply with quote

frisch wrote:
Can you run your solver on the minimal puzzles from here:

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

?


These should be much more difficult.


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
View user's profile Send private message Send e-mail Visit poster's website
gsf

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

Items
PostPosted: Wed Nov 30, 2005 7:12 pm    Post subject: Reply with quote

frisch wrote:
Can you run your solver on the minimal puzzles from here:
http://www.eleves.ens.fr/home/frisch/sudoku.html
These should be much more difficult.

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

Joined: 24 Aug 2005
Posts: 80
:

Items
PostPosted: Wed Nov 30, 2005 9:53 pm    Post subject: Reply with quote

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

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

Items
PostPosted: Thu Dec 01, 2005 2:37 am    Post subject: Reply with quote

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
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 Dec 01, 2005 5:04 am    Post subject: Reply with quote

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
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 Dec 01, 2005 6:34 am    Post subject: Reply with quote

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
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 Previous  1, 2, 3, 4, 5  Next
Page 4 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