rookery numbers

Everything about Sudoku that doesn't fit in one of the other sections

rookery numbers

Postby dukuso » Tue Jun 22, 2010 8:35 am

for any sudoku and any digit d from {1,2,..,9} we can calculate the number of 1-rookeries
that are compatible with the sudoku if d goes into that rookery.
The ordered set of the 9 numbers for the digits is the rookery-signature (better name ?)

It's invariant for our symmetry transformations and somehow indicates how difficult
the puzzle is and which what digit you should start.

e.g. for Gordon's 17-puzzle-list the rookery-signatures start :

{18,118,1,135,49,410,54,866,767}
18 118 1 135 49 410 54 1004 767
4 101 74 75 152 42 45 121 6533
1 94 2 824 116 54 79 68 6167
3 85 6 28 18 63 146 554 6720
1 33 79 108 48 11 982 706 776
31 51 1 104 54 137 665 84 1250
67 116 850 2 903 58 8 747 85
138 2 2 571 31 769 46 66 445
2 42 10 992 8 752 75 83 6616
138 2 2 35 677 573 46 66 445
2 2 66 20 445 46 138 677 769
5 50 86 96 60 136 45 725 879
1 105 40 14 590 158 171 618 1124
3 52 4 87 91 90 84 691 6546
32 1 112 184 152 509 49 96 878
37 1 12 184 184 509 49 70 6237
37 1 12 184 184 509 49 585 940
...

is there a thread, what was it called,
is there a program to quickly calculate these
is it related to the number of clues to the difficulty-rating
for given signature find a sudoku with that signature

would you like see the signature when trying to solve a sudoku,
should newspapers display it ?
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: rookery numbers

Postby dukuso » Tue Jun 22, 2010 11:25 am

this list of hard sudokus


Code: Select all
rating:   5590 ,  .......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...
rating:   2867 ,  ........3..1..56...9..4..7......9.5.7.......8.5.4.2....8..2..9...35..1..6........
rating:   1862 ,  1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1
rating:   3028 ,  ........7..9.5.2..1....6.8....5..6...9.....3...64.2....8.6.......4.2.9..7......61
rating:   3107 ,  ........6..5..8.9..3.4..7....491........8..4.5....42....1..9.5..6....4.37........
rating:   3067 ,  ........7..1..9.8..3.6..5.9.9..25.......6....3..9...4...7....91.2.5..3..8........
rating:   3485 ,  .......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....
rating:   5266 ,  .......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...
rating:   1979 ,  1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1
rating:   2974 ,  ........3..1..56...9..4..7......9.5.7.......8.5.4.2....8..2..9...35..1..6........
rating:   3794 ,  ........5..8..79...6..1..4....1.2.7.4...7...3.7.6......3..2..6...5...8..9.......7
rating:   3411 ,  .......1...6....23.2..3.4..8....5....3..1...4..96........9..7...1..2..4.5....8...
rating:   6746 ,  ....9..5..1.....3...23..7....45...7.8.....2.......64...9..1.....8..6......54....7
rating:   5467 ,  ...1....8.7......9..3.9.5....8.3...57....23.....4..6....6.8..5.4....1...2........
rating:   6194 ,  ...2....87.......9..3.9.5....8.3...51.....3.....4..6....6.8..5..7...1...2....4...
rating:   5374 ,  ...1....87.......9..6.9.5....8.6...5.....23...7.4..6....3.8..5..2...1....4.......
rating:   5367 ,  .....1.....7.2.....9.6.8..5..1..7....6.9....42.9.........8...59.8....4....6.3...8
rating:   4541 ,  ........8..3...4...9..2..6.....79.......612...6.5.2.7...8...5...1.....2.4.5.....3
rating:   6604 ,  ....9..5..1.....3...23..7....45...7.8.....2.......64...9..1.....8..6......54....7
rating:   4555 ,  1.......2....1..3...5..34....2..1..4....8.7..6..9.......1..5.4.8.....5..9...6....
rating:   3614 ,  ..2...7...1.....6.5......18....37.......49.....41.23....3.2.9...8.....5.6.......2
rating:   4752 ,  ........2..8.1.9..5....3.4....1.93...6..3..8...37......4......53.1.7.8..2........
totalnodes:9365375  time:1705/91sec.





has rookery-signatures:

{65,111,109,34,12,50,73,24,47}
{34,150,66,154,9,68,66,65,7}
{41,39,130,32,18,41,8,148,18}
{38,16,316,72,122,2,52,64,10}
{72,353,35,3,10,43,50,122,16}
{41,70,10,263,16,122,51,58,3}
{47,37,108,38,32,96,52,12,16}
{65,111,109,34,12,50,73,24,47}
{41,39,130,32,18,41,8,148,18}
{34,150,66,154,9,68,66,65,7}
{123,118,89,70,51,7,6,24,58}
{9,23,19,56,24,39,342,36,37}
{49,78,180,18,10,67,66,67,49}
{67,49,21,55,61,115,64,8,142}
{37,48,18,67,66,116,67,9,174}
{67,49,117,41,62,21,66,8,146}
{43,37,241,85,105,36,33,16,6}
{159,6,43,50,40,18,162,43,88}
{49,78,180,18,10,67,66,67,49}
{8,69,81,50,7,56,386,74,48}
{32,4,14,138,50,50,130,50,110}
{26,43,4,67,50,238,94,12,105}


almost balanced {50,50,50,50,50,50,50,50,50} seems to make hard puzzles, as expected
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: rookery numbers

Postby coloin » Tue Jun 22, 2010 2:17 pm

gsfs solver has this command
Code: Select all
%+#r#.P

Code: Select all
Easter Monster
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1

Code: Select all
8.18.18.32.39.41.41.130.148


This looks the same as yours - of course only one digit template actually fits in the puzzle.......

from here

But not taken furthur...... A well balanced puzzle will have all high numbers. Or perhaps the highest minimum number is important. The number of clues and whether 8 or 9 digit values also affects it.
coloin
 
Posts: 1632
Joined: 05 May 2005

Re: rookery numbers

Postby dukuso » Tue Jun 22, 2010 3:32 pm

OK, presumably too slow to be useful or a solver.
You get a maximum clique or tiling problem.
It could be useful for heuristic quickly finding a solution in larger
puzzles.

does it work for you under Windows ?
what's the whole command, I get "cannot read"
will have to study this %#'.+ - stuff
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: rookery numbers

Postby gsf » Tue Jun 22, 2010 3:55 pm

dukuso wrote:OK, presumably too slow to be useful or a solver.
You get a maximum clique or tiling problem.
It could be useful for heuristic quickly finding a solution in larger
puzzles.

does it work for you under Windows ?
what's the whole command, I get "cannot read"
will have to study this %#'.+ - stuff

that would be a format for the -f option: -f%+#r#.P
this should work in windows (where g.exe == sudoku.exe == gsf solver)
Code: Select all
g -f"{%+#r#,P}" .......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: rookery numbers

Postby dukuso » Tue Jun 22, 2010 4:33 pm

yes :-)
but slow.
it might be quite fast with lookups
another way to convert a sudoku into an exact cover problem
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: rookery numbers

Postby gsf » Tue Jun 22, 2010 5:16 pm

dukuso wrote:yes :-)
but slow.
it might be quite fast with lookups
another way to convert a sudoku into an exact cover problem

right, add -q- to turn off the solver
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: rookery numbers

Postby daj95376 » Tue Jun 22, 2010 5:31 pm

Using Rookeries/Templates to gauge the difficult of a puzzle went around in circles from what I recall -- coloin's link.

As for your counts, they appear to be on the initial puzzle before any attempts are made to solve it. When I compute Template counts, I do so after reducing the puzzle through SSTS and a few other common techniques.

For this puzzle:

.......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...

your rookery-signatures goes from:

{65,111,109,34,12,50,73,24,47}

to my Template counts after the Hidden Single:

{65,111,94,34,12,50,73,24,47}

Using my approach on Gordon's 17s, the Template counts are going to be {1,1,1,1,1,1,1,1,1} for most of the puzzles.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: rookery numbers

Postby dukuso » Wed Jun 23, 2010 7:31 am

faster with -q-
~60s for Gordon's 50000 17s

I'd like to create DOS batch-files for the several tasks, so I needn't remember the
symbols but % is being used - trying to figure out how to do it ... ahh, double %%
rosi.bat :
gsf4 -q- -f%%+#r#.P %1

is there a program that creates the rookery-exact-cover matrix from a sudoku ?
(should be easy, but I don't remember my old programs so well)
is it somehow equivalent to the usual exact-cover-matrix ?
faster/slower to solve for 9x9,16x16,25x25,QWHs ?
dukuso
 
Posts: 479
Joined: 25 June 2005


Return to General