QWH, order 30

dukuso · Posted: Tue Aug 30, 2005 4:42 am Post subject: QWH, order 30

here is a QWH-problem of order 30.
QWH means : "quasigroup with holes" , or latin square with holes.
It's just a sudoku, where you have no constraints with the blocks,
just with the rows and columns. And there can be multiple solutions.
These are frequently used in math-research,
see e.g. http://mat.gsia.cmu.edu/COLOR04
where this problem was picked
(qwhdec.order30.holes316 GOM) .

I'm curious whether such problems can be solved by hand
by sudoku-specialists, or by common 9*9-sudoku computer-solvers,
how far you get and what sort of problems you encounter.

If there is no answer, I'll post smaller problems...

rallveird · Posted: Sun Sep 04, 2005 5:27 pm Post subject:

I'm publishing puzzles with no box contrains now. These will still only have 1 solution though.

http://www.menneske.no/sudoku/nobox/3/eng/

dukuso · Posted: Mon Sep 05, 2005 9:17 am Post subject:

thanks, rallveird.

these are hardest usually, when there are about n^1.55*1.7 holes.
So about 330 holes for 30*30 puzzles.

I wonder how the corresponding formular would look like for sudokus.

I had to do a random restart of my solver for some of the problems.
Hardest were 10,16

menneske 30*30 problems:
-------------------------------------------------------------
01: 1 sol. 9503 nodes 260 guesses 5/91sec 629078
02: 1 sol. 50633 nodes 1652 guesses 35/91sec 1004177
03: 1 sol. 239280 nodes 5779 guesses 145/91sec 2470947
04: 1 sol. 43088 nodes 1541 guesses 30/91sec 938221
05:-1 sol. 4000001 nodes 164207 guesses 2855/91sec 37981525
05: 1 sol. 10313 nodes 343 guesses 15/91sec 720924
06: 1 sol. 1558 nodes 30 guesses 0/91sec 560264
07: 1 sol. 1008851 nodes 35263 guesses 690/91sec 9611985
08: 1 sol. 3028483 nodes 113964 guesses 2085/91sec 27837969
09: 1 sol. 1772545 nodes 66739 guesses 1310/91sec 17688410
10:-0 sol. 4000001 nodes 171670 guesses 2960/91sec 39326524
10:-1 sol. 4000001 nodes 157133 guesses 3300/91sec 43798114
10: 1 sol. 110627 nodes 4519 guesses 95/91sec 1764491
11: 1 sol. 735 nodes 8 guesses 0/91sec 556791
12: 1 sol. 18283 nodes 494 guesses 10/91sec 705918
13: 1 sol. 869 nodes 6 guesses 0/91sec 569014
14: 1 sol. 2320237 nodes 87560 guesses 1595/91sec 21444797
15: 1 sol. 46815 nodes 1508 guesses 30/91sec 949283
16:-0 sol. 4000001 nodes 158706 guesses 2810/91sec 37351163
16: 1 sol. 673014 nodes 26158 guesses 570/91sec 8001862
17: 1 sol. 85938 nodes 2469 guesses 55/91sec 1298760
18:-0 sol. 4000001 nodes 217708 guesses 3255/91sec 43171890
18: 1 sol. 12690 nodes 354 guesses 15/91sec 748328
19: 1 sol. 89864 nodes 2605 guesses 60/91sec 1305462

frisch · Posted: Tue Nov 22, 2005 10:16 pm Post subject:

What is the question of the original post? Finding a solution is easy, but there are a lot of them! Is the problem about counting solutions?

dukuso · Posted: Wed Nov 23, 2005 4:27 am Post subject:

frisch · Posted: Wed Nov 23, 2005 7:57 am Post subject:

Do you have a list of Menneske's puzzles in computer-readable form?

frisch · Posted: Wed Nov 23, 2005 11:03 am Post subject:

My timings for the 19 30x30 puzzles:

Puzzle 1: time: 9.263992 ms
Puzzle 2: time: 6.855965 ms
Puzzle 3: time: 11.114120 ms
Puzzle 4: time: 5.496979 ms
Puzzle 5: time: 7.850885 ms
Puzzle 6: time: 8.049011 ms
Puzzle 7: time: 5.131960 ms
Puzzle 8: time: 19.749880 ms
Puzzle 9: time: 27.758121 ms
Puzzle 10: time: 13.806820 ms
Puzzle 11: time: 12.109995 ms
Puzzle 12: time: 9.523869 ms
Puzzle 13: time: 12.587786 ms
Puzzle 14: time: 7.427931 ms
Puzzle 15: time: 13.041019 ms
Puzzle 16: time: 9.640932 ms
Puzzle 17: time: 14.419794 ms
Puzzle 18: time: 9.363174 ms
Puzzle 19: time: 8.731842 ms

frisch · Posted: Wed Nov 23, 2005 1:55 pm Post subject:

Ok, I started to minimize the first one.

Here is the first result:

dukuso · Posted: Thu Nov 24, 2005 10:36 pm Post subject:

35sec for me to solve.
how long does it take to minimize 30*30 QWHs ?
is it random ?

369 holes , that't 1.89*30^1.55, a little above phase transition.

Can we figure out the phase-transition-formula for sudokus
by creating minimal ones ?

we have
minimal sudokus:
9*9 : 57 holes
16*16 : 165 holes
25*25 : about 350 holes

minimal QWHs
25*25 : 267 holes = 1.82*25^1.55

frisch · Posted: Fri Nov 25, 2005 6:56 pm Post subject:

I started again my minimization algorithm (now, it chooses the clues to remove randomly). It took 17 minutes to run on a P4 3.2 Ghz.

dukuso · Posted: Sat Nov 26, 2005 4:55 am Post subject:

this was solved in 6min with my old program and 4sec with
my new, which was a surprise to me. Usually I don't get such differences.
I haven't checked, there could be a bug.

here's one other benchmark from a Regin+Gomes paper. :
www.constraint-programming.com/ people/regin/papers/cardmatrix.pdf

Apparantly it was first solved in 2004 in 9900s .
The solution is somehow obvious to a human, but can your
solver find it ?

qwh order 35, 405 holes:

gsf · Posted: Wed Nov 30, 2005 7:07 pm Post subject:

frisch · Posted: Fri Dec 02, 2005 6:07 pm Post subject:

I've posted some more minimal 30x30 QWH at the usual place:

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

Enjoy!

-- Alain

dukuso · Posted: Sat Dec 03, 2005 3:14 am Post subject:

Satz: 58s
Satzoo: 230s
Guenter: 423s

for these 9. #7 and #9 are hardest

dukuso · Posted: Sat Dec 03, 2005 3:19 am Post subject: