Oct-doku

For fans of Killer Sudoku, Samurai Sudoku and other variants

Oct-doku

Postby coloin » Tue Sep 09, 2008 5:34 am

Oct-doku

Another varient I dreamt up ! Probably only useful as "tea-time quickies"

Same as 9*9 Vanilla sudoku

But only eight clue values and a blank cell in each box.

Possibly already described

Code: Select all
+---+---+---+
|*..|...|...|
|...|*..|...|
|...|...|*..|
+---+---+---+
|.*.|...|...|
|...|.*.|...|
|...|...|.*.|
+---+---+---+
|..*|...|...|
|...|..*|...|
|...|...|..*|
+---+---+---+


I can use my vanilla programs to give this 13-clue example [probably the minimum] [plagered from a 17 with x4 of one clue value]


Code: Select all
+---+---+---+
|*23|...|...|
|4..|*1.|...|
|...|...|*5.|
+---+---+---+
|.*.|...|.6.|
|..5|.*.|...|
|...|.3.|.*4|
+---+---+---+
|..*|6..|...|
|...|5.*|7..|
|3..|...|..*|
+---+---+---+   "mild"


Might be useful for unaswered questions re vanilla 17s/18s ?

Probably a vanilla 17 with x5 of one clue value doesnt exist.

Which would indicate a 12-clue oct-doku doesnt exist - unless we are able to find a 18-clue vanilla with x6 of one clue value.

Time will tell.

C
Last edited by coloin on Tue Sep 09, 2008 6:09 am, edited 1 time in total.
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby tarek » Tue Sep 09, 2008 6:44 am

So :

1. You uncovered the nine positions of a certain clue in a vanilla puzzle .....
2. Minimized the puzzle so that only the minimal puzzles with 8 positions are present & uncovered
3. cover up those 8 positions ......

Is that correct ?

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby coloin » Tue Sep 09, 2008 7:36 am

Sort of, not sure about 3.

Code: Select all
+---+---+---+
|923|...|...|
|4..|91.|...|
|...|...|95.|
+---+---+---+
|.9.|...|.6.|
|..5|.9.|...|
|...|.3.|.94|
+---+---+---+
|..9|6..|...|
|...|5.9|7..|
|3..|...|..9|
+---+---+---+  mild


This is a 22-clue vanilla non-minimal puzzle

5 clues of the 9-rookery can be removed to leave us with a 17-clue vanilla.
Code: Select all
+---+---+---+
|.23|...|...|
|4..|.1.|...|
|...|...|95.|
+---+---+---+
|.9.|...|.6.|
|..5|...|...|
|...|.3.|..4|
+---+---+---+
|..9|6..|...|
|...|5.9|7..|
|3..|...|...|
+---+---+---+ 17 clue from gordon's list


Removing all the 9s leaves a 13-clues oct-duku [as in post above].

Ive posted to gsf to see if there is mileage in making vanilla 17s utilizing the oct-duku reductions !

Essentially the blank cells are fixed in one position.
There are only 8 clues [only 7 clue values needed]
There are only 72 potential cells

How many different 14-clue oct-duku puzzles are there ?
- there are usually several from each vanilla-17.


How easy is it to generate random 15-clue oct-doku puzzles ?

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby coloin » Tue Sep 09, 2008 9:39 am

Ah Ha

you will recognize this oct-duko puzzle

Code: Select all
+---+---+---+
|...|8..|.39|
|8..|..1|..5|
|..3|.5.|8..|
+---+---+---+
|..8|.9.|..6|
|.7.|..2|..8|
|1..|4.8|...|
+---+---+---+
|..9|.8.|.5.|
|.2.|...|68.|
|48.|7..|...|
+---+---+---+  Gonden Nuggett with 6 more "8"s SE 9.3

scrambled to the format
Code: Select all
+---+---+---+
|*..|.1.|.5.|
|...|*..|.83|
|.3.|..5|*..|
+---+---+---+
|.*.|..8|.6.|
|1..|4*.|...|
|..7|.2.|.*.|
+---+---+---+
|4.*|7..|...|
|.8.|..*|..5|
|..2|...|6.*|
+---+---+---+ SE still presumably 9.3


Hmmmm

How easy is it to generate these puzzles again ?

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Pat » Tue Sep 09, 2008 9:51 am

you can call it a "13-clue" oct-duko --
but it is equivalent to a plain SuDoku puzzle
having 13 + 9 = 22 clues
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Postby coloin » Tue Sep 09, 2008 10:01 am

Yes they are equivalent. And yes you are right - Oct-Doku is what it should be coined.

But what is it doing to the "sudoku puzzle space ?"

Another one from the hardest archive

Code: Select all
+---+---+---+                            +---+---+---+                                     
|1..|...|...|                            |1..|...|...|                                           
|.2.|4..|.6.|                            |.2.|4..|.6.|                                           
|..3|...|5.1|                            |4.3|...|5.1|                                           
+---+---+---+                            +---+---+---+                                           
|.4.|.86|...|                            |.4.|.86|...|                                           
|...|.49|.8.|                            |...|.49|.8.|                                           
|...|2..|...|                            |...|2..|...|                                           
+---+---+---+                            +---+---+---+                                           
|5.7|...|3..|                            |5.7|..4|3..|                                           
|.6.|9..|.4.|                            |.6.|9..|.4.|                                           
|...|...|..7|                            |..4|...|..7|                                           
+---+---+---+   "cloudy bay" SE 10.9,    +---+---+---+    with 4 singles inserted !

http://forum.enjoysudoku.com/viewtopic.php?t=4212&start=840

scrambled and the rookery completed
Code: Select all
+---+---+---+                                                                               
|9.1|...|43.|                                                                                     
|.2.|9..|..5|                                                                                     
|3..|...|9..|                                                                                     
+---+---+---+                                                                                     
|.9.|.85|...|                                                                                     
|...|.96|..8|                                                                                     
|...|2..|.9.|                                                                                     
+---+---+---+                                                                                     
|..9|...|.7.|                                                                                     
|4.7|..9|1..|                                                                                     
|.5.|6..|..9|                                                                                     
+---+---+---+   with the 4 clue rookery filled SE    10.5

reduced to oct-doku
Code: Select all
+---+---+---+
|*.1|...|43.|
|.2.|*..|..5|
|3..|...|*..|
+---+---+---+
|.*.|.85|...|
|...|.*6|..8|
|...|2..|.*.|
+---+---+---+
|..*|...|.7.|
|4.7|..*|1..|
|.5.|6..|..*|
+---+---+---+   SE presumably still a whopping 10.5

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby tarek » Tue Sep 09, 2008 11:54 am

there is still something confusing about this coloin,

if we KNOW 9 positions of a clue then the extra non minimal clues would allow removal of other clues outside this this 9 position clue...

Minimality is then achived when removal of a clue would result in multiple solutions....

I think you may be able to achieve less than 13 with that 17 clue seed from gordon's list (if you can remove redundant clues other than 9s in the 22 clue version)

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby coloin » Wed Sep 10, 2008 4:55 am

tarek wrote:if we KNOW 9 positions of a clue then the extra non minimal clues would allow removal of other clues outside this this 9 position clue.......I think you may be able to achieve less than 13 with that 17 clue seed from gordon's list (if you can remove redundant clues other than 9s in the 22 clue version)tarek


In the puzzles with less than 15 clues there are not many of these 15 that can be removed from a 15 plus 9 vanilla.

I agree in oct-doku puzzles with around 20 clues many of the 20 can be removed from a 20 plus 9 vanilla.

The search space is being compressed - especially for the 14 clue oct-doku. That is why I think we could generate them

We already have many from Gordon's list [all the puzzles with a 14 plus 3 configuration] [Almost all of Gordon's list have this configuration].
[18-puzzles with a 14 plus 4 configuration]
[19-puzzles with a 14 plus 5 configuration]
[20-puzzles with a 14 plus 6 configuration] [?exists]

The search space is being compressed - there is one less clue value and 9 less clue positions for these 14 clues - but I dont know if these puzzles are within doable limits. They are possibly all within a {-2+2} of each other too.

Can you get a program to chuck these out ?

Im anticipating a confirmatory post from gsf !

Coloin
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby gsf » Wed Sep 10, 2008 9:44 am

coloin wrote:Can you get a program to chuck these out ?

Im anticipating a confirmatory post from gsf !

its a neat idea
won't have anything this week though
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Wed Sep 10, 2008 9:54 am

OK gsf
BTW whats the code which performs this count

Code: Select all
      7      15    011122334
    175     226    011123333
    197     315    011222234
   5908    7537    011222333
     12      25    012222224
   8377   10028    012222233
    730     850    022222223
     10      15    111113333
     81     121    111122234
   2220    2847    111122333
     13      21    111222224
  11091   13394    111222233
   4104    4696    112222223
      5       5    122222222
-------  ------             
  32930   40095 


tarek wrote:I think you may be able to achieve less than 13 with that 17 clue seed from gordon's list (if you can remove redundant clues other than 9s in the 22 clue version) tarek


Yes you may be able to remove a clue other than the nine.

This would be a 12 plus 9 scenario.

It cant be a 12 plus 5 {I dont think there are any of these in Gordons list}{see above]

The best it can be would be a 12 plus 6 = 18 clue vanilla

[You cant have a minimal puzzle with 7 clues in a rookery !]

Interesting if we were to find a 12.

If we can generate all the 14s, we can easily test these all for new 17s......and put this little matter to rest.

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby gsf » Wed Sep 10, 2008 12:04 pm

coloin wrote:OK gsf
BTW whats the code which performs this count

Code: Select all
      7      15    011122334
    175     226    011123333
    197     315    011222234
   5908    7537    011222333
     12      25    012222224
   8377   10028    012222233
    730     850    022222223
     10      15    111113333
     81     121    111122234
   2220    2847    111122333
     13      21    111222224
  11091   13394    111222233
   4104    4696    112222223
      5       5    122222222
-------  ------             
  32930   40095 


refresh me on what the columns represent
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Wed Sep 10, 2008 12:20 pm

Sorry, they are the distribution of clue values in Gordons 17-puzzles. Note no "********5" in the list.

Code: Select all
+---+---+---+
|.23|...|...|
|4..|.1.|...|
|...|...|95.|
+---+---+---+
|.9.|...|.6.|
|..5|...|...|
|...|.3.|..4|
+---+---+---+
|..9|6..|...|
|...|5.9|7..|
|3..|...|...|
+---+---+---+


This is the clue value occurance in this puzzle [011122334]
1-1 times
2-1 times
3-3 times
4-2 times
5-3 times
6-2 times
7-1 times
8-0 times
9-4 times

I want to look at a batch of 18s

I doubt whether there is a minimal [011122236]

If there is - it means there is a 12 clue oct-doku.
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby gsf » Wed Sep 10, 2008 1:01 pm

coloin wrote:Sorry, they are the distribution of clue values in Gordons 17-puzzles. Note no "********5" in the list.

generated by my solver and a few unix commands
Code: Select all
sudoku -f%+#oP g.dat | sort | uniq -c

where g.dat is Gordon's catalog
the result for the current 17s
Code: Select all
   26 011122334
  295 011123333
  470 011222234
 9598 011222333
   32 012222224
11734 012222233
  947 022222223
   22 111113333
  170 111122234
 3586 111122333
   33 111222224
15761 111222233
 5227 112222223
    8 122222222
-----
47909
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Wed Sep 10, 2008 2:25 pm

My lack of knowledge of the sudoku space shows ....

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby coloin » Wed Sep 10, 2008 3:21 pm

No cigar yet........

The "sudoku puzzle space" issue is vast - but at least its finite !

For every way of completing a 14 clue oct-doku there will be many of the isomorphs which will have the identical blank cell [9 clue] rookery.

1 per each of the 9 boxes = x9
diagonal reflection = x2
[and of course the 8!]

Edit - this is less than I first calculated.

Looking at a few distributions from the puzzle archives
[11122335] & [011222235] did occur - but very much at the edge of the 18-space.

Code: Select all
011123334       205
011133333      1172
011222235         2
011222244         3
011222334      2294
011223333     43721
012222234      1740
012222333     94817
022222224         4
022222233     17691
111113334        10
111122334       845
111123333     12350
111222234      2495
111222333    114942
112222224        59
112222233     97709
122222223      8506
222222222         8
                   
Total        398573

Not many [< ~ 2%] [********4] in the 18s
Not many [********5] on a batch of 19s either.

There would have to be an awful lot of these 14 clues to overwhelm us now.

Following on, it isnt too hard to test/add 3 clues into 9 spaces for all of these.

Worringly, doing a {-2+2} on 14-plus-9 - isnt a very productive or quick way of making new 14-clue oct-doku puzzles......:(
Selectivly removing 3 clues and adding 3 more didnt have a good yield either.......

Attempting a {-1+2} on a 13-plus-9 oct-doku.......this did generate new 14 plus 9 puzzles.......

If we were to find a 12-plus-9 oct-doku......that might just make it a bit easier !:(

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Next

Return to Sudoku variants