13-clue Sudoku X

For fans of Killer Sudoku, Samurai Sudoku and other variants

13-clue Sudoku X

Postby gfroyle » Sat Dec 31, 2005 11:11 am

Here is a 13-clue Sudoku X (ie diagonal + antidiagonal added as extra blocks that must contain no repeated numbers)

Code: Select all
1 0 0  0 0 4  0 0 0 
0 0 0  0 0 0  0 9 0 
0 0 0  6 0 0  0 0 0 

0 0 5  0 3 0  0 0 0 
0 0 0  0 0 0  0 2 9 
0 6 0  0 0 0  0 0 0 

0 0 0  0 0 6  0 0 0 
0 0 0  0 0 0  0 0 0 
0 3 8  0 0 0  5 0 0


Enjoy!

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby Moschopulus » Sat Dec 31, 2005 10:14 pm

It's interesting to see we can go as low as 13. I wonder if there is a 12?

I assume you found this with the same algorithm as for ordinary sudoku? You took the 14 that you posted before, and did some perturbations of it. You must also have modified your solver for sudoku X.

I was wondering about unavoidable sets for sudoku X. Suppose we start with a sudoku-X puzzle that has a unique solution. I suppose we define as before: an unavoidable set (in the solution grid) is a set of cells such that some permutation of those cells results in another valid completed diagonal grid.

All the unavoidable sets from ordinary sudoku will be unavoidables for sudoku X if they do not have any cells on the diagonals.

If an unavoidable set from ordinary sudoku has one cell on a diagonal, for example {11,12,41,42}, then it will definitely *not* be an unavoidable set for sudoku X.

Unavoidable sets from ordinary sudoku that hit the diagonals in two more more cells might remain unavoidable, if the permutation from ordinary sudoku happens to also permute the diagonals. It looks to me that this may or may not happen.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby ihope127 » Sun Jan 01, 2006 5:33 am

Wait, just what are the new can't-be-the-same groups?
ihope127
 
Posts: 22
Joined: 25 December 2005

Postby gfroyle » Sun Jan 01, 2006 8:36 am

ihope127 wrote:Wait, just what are the new can't-be-the-same groups?


The diagonal (marked with X)

Code: Select all
X 0 0  0 0 4  0 0 0 
0 X 0  0 0 0  0 9 0 
0 0 X  6 0 0  0 0 0 

0 0 5  X 3 0  0 0 0 
0 0 0  0 X 0  0 2 9 
0 6 0  0 0 X  0 0 0 

0 0 0  0 0 6  X 0 0 
0 0 0  0 0 0  0 X 0 
0 3 8  0 0 0  5 0 X


and the anti-diagonal (marked with X)

Code: Select all
1 0 0  0 0 4  0 0 X 
0 0 0  0 0 0  0 X 0 
0 0 0  6 0 0  X 0 0 

0 0 5  0 3 X  0 0 0 
0 0 0  0 X 0  0 2 9 
0 6 0  X 0 0  0 0 0 

0 0 X  0 0 6  0 0 0 
0 X 0  0 0 0  0 0 0 
X 3 8  0 0 0  5 0 0


Please feel free to check that I am correct - the program for these is a variant of my well-tested program, and I usually introduce a bug or two when changing programs...

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

unavoidables in sudoku X

Postby Moschopulus » Mon Jan 02, 2006 2:43 pm

Suppose you have a completed diagonal grid (1-9 on both diagonals), and an unavoidable set for this grid from ordinary sudoku. You want to know if this set remains an unavoidable set for sudoku-X. One way is just to remove the unavoidable set, and run the remaining puzzle through a sudoku-X solver. The set is unavoidable for sudoku-X if and only if the solver says there are at least two solutions.

It looks like most of the unavoidables from ordinary sudoku are lost, so the MCN for sudoku-X will be much smaller then the MCN for the same grid for sudoku.

Edit: for example, the solution grid of the 13 given above is
123984675654713298879625314915432786387561429462897153291356847546278931738149562
The MCN for ordinary sudoku for this grid is 10, whereas the MCN for sudoku-X is 4. For ordinary sudoku there are 24 unavoidables of size 4 or 6, whereas for sudoku-X there are 3 of size 4 or 6 (only 3 of the 24 survive).
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Re: 13-clue Sudoku X

Postby pompy » Fri Apr 21, 2006 4:40 pm

gfroyle wrote:Here is a 13-clue Sudoku X (ie diagonal + antidiagonal added as extra blocks that must contain no repeated numbers)

Code: Select all
1 0 0  0 0 4  0 0 0 
0 0 0  0 0 0  0 9 0 
0 0 0  6 0 0  0 0 0 

0 0 5  0 3 0  0 0 0 
0 0 0  0 0 0  0 2 9 
0 6 0  0 0 0  0 0 0 

0 0 0  0 0 6  0 0 0 
0 0 0  0 0 0  0 0 0 
0 3 8  0 0 0  5 0 0


Enjoy!

Gordon


DELETED
pompy
 
Posts: 1
Joined: 21 April 2006

Postby Chessmaster » Fri Apr 21, 2006 8:27 pm

that is cool. i doubt you can go lower than that. it is like 17 clues for the regular sudoku
Chessmaster
 
Posts: 191
Joined: 21 December 2005

Found a 12

Postby Ruud » Mon Jul 23, 2007 5:41 pm

While everybody is searching for 17-clue Sudokus, I spent this weekend in another niche, using similar searching techniques.

Here's a Sudoku-X with 12 clues:

[img]http://www.sudoku.org.uk/discus/messages/743/4446.png[/img] { broken link }

000000009050000010000005000000000060000007000000004000000100000000920000004000008

A new record, if I'm not mistaking.:D

I found a few hundred in total, which I will post on my website after canonicalization and filtering out the duplicates.

Searching for an 11 now...

Ruud
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby JPF » Mon Jul 23, 2007 6:24 pm

Congratulations:)

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby ravel » Mon Jul 23, 2007 6:26 pm

Congrats on that one, Ruud.

It must be an easy one, because i could solve it:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby udosuk » Mon Jul 23, 2007 6:29 pm

Congrats Ruud!:) Good luck looking for the 11.

I wonder how close we can get to the minimum 8...

On the other hand, I bet you can do better if you work on Windoku X or DG X...

PS:

A warning for all Simple Sudoku users, don't try to load this puzzle onto that program and start solving, otherwise your CPU will be preoccupied for a long time when SS tries ferociously working out the number of (non-X) solutions.:!: You should start solving on SS using a blank puzzle and then manually key in the 12 clues at the beginning.:idea:

Guess the number of non-X solutions for this puzzle hits the "black-hole" range of SS's programming (if SS detects the number of solutions to be over a certain limit, say 1 million, it aborts counting and reports "too many solutions", so if the number of solutions is just below that limit, SS will suck all your CPU power to work it out).
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Ruud » Mon Jul 23, 2007 11:51 pm

The current collection can be downloaded from my website at this page, where I also explain my search methods.

The current collection has 1167 canonicalized Sudoku-X puzzles with 12 clues. This collection is exhausted for the -1+1 search method. No elevens were found. I will sleep better if anyone (gsf?) can confirm that the puzzles are unique upto isomorphism.

The first puzzle in the collection (also shown on the page) starts with a series of 33:!: empty cells.

Ruud
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby udosuk » Tue Jul 24, 2007 9:29 am

Ruud wrote:The first puzzle in the collection (also shown on the page) starts with a series of 33:!: empty cells.

That puzzle is a beast. Do you have any elegant scheme to solve it?

"Normal" techniques bring us to this state:
Code: Select all
 *-----------------------------------------------------------------------------*
 | 6       35789   379     | 1       4      #359     | 2       5789    39      |
 | 4       2       379     | 5789   @3579   #359     | 35789   6       1       |
 | 3589    35789   1       | 56789  -23579   26      | 3579    5789    4       |
 |-------------------------+-------------------------+-------------------------|
 | 379     6       379     | 59      8       4       | 1       2       57      |
 | 789     789     2       | 3      @59      1       | 6       4       57      |
 | 1       4       5       | 2       6       7       | 389     89      39      |
 |-------------------------+-------------------------+-------------------------|
 | 2       3579    8       | 579     13579   359     | 4       1579    6       |
 | 579     1       6       | 4      @579     8       | 579     3       2       |
 | 3579    3579    4       | 5679    123579  26      | 59      1579    8       |
 *-----------------------------------------------------------------------------*

ALS-xz:
ALS A (@): r258c5={3579}
ALS B (#): r12c6={359}
restricted common: x=3
common: z=9

Therefore r3c5<>9.
Code: Select all
 *-----------------------------------------------------------------------------*
 | 6       35789  *379     | 1       4      *359     | 2       5789   -39      |
 | 4       2      *379     |*5789   *3579   *359     | 35789   6       1       |
 | 3589    35789   1       |*56789   2357    26      | 3579    5789    4       |
 |-------------------------+-------------------------+-------------------------|
 | 379     6      *379     |*59      8       4       | 1       2       57      |
 | 789     789     2       | 3      #59      1       | 6       4       57      |
 | 1       4       5       | 2       6       7       | 389     89      39      |
 |-------------------------+-------------------------+-------------------------|
 | 2       3579    8       | 579     13579   359     | 4       1579    6       |
 | 579     1       6       | 4       579     8       | 579     3       2       |
 | 3579    3579    4       | 5679    123579  26      | 59      1579    8       |
 *-----------------------------------------------------------------------------*

Mutant Sashimi Swordfish (c3+b2+b5/r1+r2+r4c4 with fin @ r5c5): r1c9<>9 => r1c9=3
(Logic:
If r5c5=9, r1c9<>9 (d/).
If r5c5<>9, r4c4=9 => the 9s in c3 & b2 form a grouped x-wing @ r12c356 => r1c9<>9.
Therefore r1c9<>9 no matter what.)

After singles and box-line interactions and a simple turbot fish on 9s:
Code: Select all
 *--------------------------------------------------------------------*
 | 6      8      7      | 1      4      9      | 2      5      3      |
 | 4      2      9      | 57     357    35     | 8      6      1      |
 | 3      5      1      | 8      2      6      |@79     79     4      |
 |----------------------+----------------------+----------------------|
 |@79     6      3      |*59     8      4      | 1      2      57     |
 | 8      79     2      | 3     *59     1      | 6      4      57     |
 | 1      4      5      | 2      6      7      | 3      8      9      |
 |----------------------+----------------------+----------------------|
 | 2      37     8      | 579    13579  35     | 4      179    6      |
 | 579    1      6      | 4      79     8      | 579    3      2      |
 |-579    379    4      | 6      1379   2      | 59     179    8      |
 *--------------------------------------------------------------------*

Y-Wing (W-Wing/Semi-Remote Naked Pair):
Strong link of 9s between r4c4 & r5c5 + {79} @ r3c7,r4c1 => r9c1<>7.

Singles and naked pairs solve the rest.

I truly hope Ruud or anybody else has a better/shorter solution. I particular hate that mutant sashimi swordfish which I ain't even sure if I got the representation correct.:(
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Tue Jul 24, 2007 10:02 am

Ruud wrote:The current collection has 1167 canonicalized Sudoku-X puzzles with 12 clues. This collection is exhausted for the -1+1 search method. No elevens were found. I will sleep better if anyone (gsf?) can confirm that the puzzles are unique upto isomorphism.

nice job on the 12's

I coded an x canonicalizer and got the same 1167 list
but from your description I think you may have missed some symmetries
(or maybe its too late and I missed some dups)
each of these can be swapped independently (for 4 combinations including the identity)
Code: Select all
r(46)
c(46)

and each of these can be swapped independently (for 4 combinations including the identity)
Code: Select all
r(12)(89)c(12)(89)
r(13)(79)c(13)(79)
r(23)(78)c(23)(78)

factor in 4 rotational positions and 2 for transposition and that yields 4*4*4*2 = 64 symmetric positions to check

point me to some other canonicalized x with a larger clue range and I'll check them too
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Tue Jul 24, 2007 10:59 am

except for '#' at r3c4 udosuk wrote:
Code: Select all
*----------------------------------------------------------------*
| 6      35789 *379    | 1      4     *359    | 2      5789  -39 |
| 4      2     *379    |*5789  *3579  *359    | 35789  6      1  |
| 3589   35789  1      |#56789  2357   26     | 3579   5789   4  |
|----------------------+----------------------+------------------|
| 379    6     *379    |*59     8      4      | 1      2      57 |
| 789    789    2      | 3     #59     1      | 6      4      57 |
| 1      4      5      | 2      6      7      | 389    89     39 |
|----------------------+----------------------+------------------|
| 2      3579   8      | 579    13579  359    | 4      1579   6  |
| 579    1      6      | 4      579    8      | 579    3      2  |
| 3579   3579   4      | 5679   123579 26     | 59     1579   8  |
*----------------------------------------------------------------*
 

Mutant Sashimi Swordfish (c3+b2+b5/r1+r2+r4c4 with fin @ r5c5): r1c9<>9 => r1c9=3
(Logic:
If r5c5=9, r1c9<>9 (d/).
If r5c5<>9, r4c4=9 => the 9s in c3 & b2 form a grouped x-wing @ r12c356 => r1c9<>9.
Therefore r1c9<>9 no matter what.)I particular hate that mutant sashimi swordfish which I ain't even sure if I got the representation correct.:(

You didn't cover candidates r3c4 and r4c3, but there's a sashimi mutant swordfish c3b25\r124 with fins @ r5c5 & r3c4.

unfinned swordfish: c3b25\r124-9-r1c9,
fin r5c5-9-r1c9,
fin r3c4-9-r4c4=9=r5c5-9-r1c9, all imply r1c9<>9

I'm not enamored with all the adjectives either, particularly the 'sashimi' term ... and the 'franken' and 'mutant' terms are redundant when the sectors (units) are given.

[edit: for use of "mutant", see here]
Last edited by ronk on Tue Jul 24, 2007 9:58 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Sudoku variants