The New Sudoku Players' Forum

[Mathimagics]

Here is a puzzle I call Sudoku Pairs.

It is simply this - we have 2 Sudoku's combined in the one grid, as illustrated by this completed example:

SudokuPair-Example1.gif (10.7 KiB) Viewed 1761 times

The 2-digit values in each cell are labelled A and B. E.g. B(2,4) = 7. The grids corresponding to A(*,*) and B(*,*) are each valid Sudoku Squares.

But also note that every cell has a different pair value AB - that is, the numbers 11 to 99 (excluding those numbers with a 0) occur exactly once each. Mathematically speaking, A and B are mutually orthogonal, and no we can't make a puzzle from just any pair of Sudoku squares.

One remarkable feature of these puzzles is that the relationship between the two grids means that we can achieve minimality with less than 17 clues, and to prove that, here is a 15-clue example, which I hope some puzzlers will enjoy.

SudokuPair-15clues.gif (7.44 KiB) Viewed 1761 times

I suspect that I currently have the only computer-based solver, but trust that others will take up the challenge of finding even smaller minimal forms (if indeed they exist).

[tarek]

Hi Mathimagics,

The puzzles above are not far off these sudoku variants.

This is a variant which I've been working on lately & The original Thread and my 1st 3 puzzles can be found here. The concept is quite close to some other variants like Orthogonal Sudoku, Graeco-Latin Soduku & Setdoku. Sudoku^2 is different enough to justify a name on it's own: Tarek's Sudoku^2 Puzzles (Squared, Power of 2)

16 symbols for a regular 16x16 sudoku. Each symbol can be broken down into two different symbols. We end up with two groups of 4 symbols. Each group can form a regular 4x4 sudoku in each of the 16 boxes of the 16x16 sudoku!

tarek

[Mathimagics]

Interesting! I can see you've been here well ahead of me.

I came to look at these orthogonal-pair puzzles because they seem to offer an alternative way of arriving at an 81 x 81 minimal form. As noted elsewhere in this forum that seems to be a bridge too far computationally, and I wondered whether a minimal 81 x 81 orthogonal-pairs puzzle (Sudoku^2 as you called it) might be feasible.

And the minimum clues required is itself an interesting problem wrt simple Orthogonal Sudoku 9x9.

[tarek]

I started coding these with the clues being a paired clue (you have 81 paired clues on you orthogonal sudoku). The next step would be to code clues as being 162 clues. Some cells will have a paired clue and some will have only a clue from one of the subpuzzles.

Following the same principles would make you look at sudoku as having 81x9 clues which then makes it easy to code the "pencilmark sudoku" or as some would call it "Sukaku". I've gone as far as creating a backdoor 6 minimal puzzle but couldn't go any further.

Not enough memory or fire power for the 81*81 sudoku^2 and certainly a sudoku^3 is a dream waiting to be realised. Nowadays with a SAT solver and economical coding should make it a possibility

Good luck

[Mathimagics]

Excuse my ignorance, tarek, but what is a "backdoor 6 minimal puzzle"?

With paired/unpaired clues, clues don't need to be paired, but the presentation seems neater that way. And it avoids the issue of deciding how to count unpaired clues. Is it reasonable to count them as 0.5?

Nevertheless it's true I need to handle unpaired clues transparently which I currently do not. Working on it ...


[Edit] I guess the best approach is to count each clue individually, ie. the puzzle above has 30 clues.

[Mathimagics]

I have established that the puzzle as presented actually has at least 5 redundant clues. The current state of play is:

Code: Select all

  .  . 66  .  .  .  .  . x7
 8x  .  .  .  .  .  . 12  .
  .  .  .  .  .  .  .  . 88
 78  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .
  .  .  . 63  .  .  .  . 51
  .  .  .  .  .  .  . 79  .
  . 49  .  .  . 7x  . x8  .
  .  .  .  . 35  . 27  . 6x


The remaining candidate list for possible removal is

Code: Select all

12:  try 1x
88:  try 8x
51:  try x1
79:  try x9
49:  try 4x or x9
27:  try 2x


All other clues have been certified as fixed (non-removable).

The BIG problem I have is the unexpectedly long time it is taking to test individual clue removals (or perhaps not unexpectedly?).

At 30 clues (the original), I knew this case might be a tad unusual because it was the slowest to reduce in the dozen or so samples I tried. It took a DLX solver 240s to prove uniqueness of solution.

The DLX model (virtual) has a notional 6561 rows x 648 columns. It's pretty straight-forward - one value (1...81) per cell + every cell diffrent (1...81) + two sub-problems A and B, (unique A values in row, col and block), ditto for B.

For these clue sets the actual row count is between 2232 (30 clues) and 2573 (25 clues).

No worries, then, we'll crank up MiniSAT, giving it the same exact cover problem model. Unfortunately that took 20 minutes to emulate the DLX solver for 30 clues.

I then removed the half clues indicated above at (1,9) and (2,1), to give a (still unique-soln) 28-clue set. DLX took 25 minutes, MiniSAT took 3h 15m.

For obvious reasons I didn't run any more with MiniSAT - reports of it scaling better than DLX might be true for standard Sudoku, but we have a significantly different model here .

I simply guessed the clue "most likely" to prove removable and sat back patiently.

I got lucky 3 times in a row, DLX solved the 27 and 26 clue cases in 33m and 65m although it had a real conniption when I removed another clue to give 25. Just as well that turned out to be removable, because it took DLX 6.5 hours ... for confirmation.

Do I hear 24? For a "certificate of minimality" we still have to test those clues.

Sadly we have eliminated too many clues from the individual Sudokus for simple enumeration of one list (iteration cost is tiny, but there are potentially billions of solns to check) to be effective. I'm running out of ideas ... (and I have the flu: these conditions may be linked )

[tarek]

Excuse my ignorance, tarek, but what is a "backdoor 6 minimal puzzle"?

I should have qualified it. The backdoor is essentially a lucky guess that is needed to render the puzzle solvable using a specified set of techniques. A common set of techniques is singles (hidden & naked). Sudoku puzzles may not need a backdoor to solve using singles and therefore they are backdoor size 0. Some special puzzles require 3 and therefore are backdoor size 3.

Larger puzzles & sudoku variants may have larger backdoor sizes. I believe that I've found a sudoku puzzle (Sukaku) that is backdoor size 6.

When I first coded these puzzles, I was following your train of thoughts exactly!

I then coded the puzzle (for example your orthogonal sudoku) as having 162 clues. When you minimise you puzzles you can filter out the ones with the least number of cells which will increase to possibility of having 2 clues per cell if you are after more aesthetically pleasing minimal puzzles. You can also find symmetric puzzles (See my Sudoku^2)

With your versatile coding, all of these sudoku variants are at your mercy!!!

tarek

[Mathimagics]

Do I hear 24?

Indeed, I have 24, and the verification took 28.5 hours!

The time for N-1 clue testing can be anything from 2 to 4 times the N clue time. To perform the remaining tests (there are still 4 candidates for possible removal to give a 23-clue set), I have built a multiple-thread DLX test rig, using a DFS-driven divide-and-conquer strategy.

I'm testing the first candidate now, and it looks like it will complete in about 10 hours (unless it finds evidence of multiple solutions, in which case it might finish sooner than that).

The computational complexity of this apparently simple problem is really quite astonishing.
==================================================================================

First candidate was removable, took a bit longer than predicted (14 hours). So we have just 23 clues fixing a unique solution. The two Sudoku's taken individually appear to have minimum clue sets of around 20, so that's pretty amazing.

On the down side, this means that the remaining 3 clue-removal tests are now that much harder!!

[Mathimagics]

This 23-clue set appears to be fully reduced:

Code: Select all

  .  . 66  .  .  .  .  . x7
 8x  .  .  .  .  .  . 12  .
  .  .  .  .  .  .  .  . 8x
 78  .  .  .  .  .  .  .  .
  .  .  .  .  .  .  .  .  .
  .  .  . 63  .  .  .  . 51
  .  .  .  .  .  .  . 79  .
  . 4x  .  .  . 7x  . x8  .
  .  .  .  . 35  . 27  . 6x


When you minimise you puzzles you can filter out the ones with the least number of cells which will increase to possibility of having 2 clues per cell if you are after more aesthetically pleasing minimal puzzles.

It seems to me that finding reduced forms with minimal clue counts is most likely to involve paired clues, since one paired clue typically has more "oomph" (to use a technical term!) than 2 x unpaired clues, by virtue of the fact that the paired clue reduces domains globally (ie: paired value is eliminated from all cell domains).