The New Sudoku Players' Forum

[JPF]

I brought this idea in an other thread, but it was not really the right place to post it.

Let's consider this valid, minimal 24-puzzle :

Code: Select all

 . . . | . . . | . . .
 . . . | . . . | . 7 1
 . . . | . . . | 6 9 8
-------+-------+-------
 . . 4 | . . . | . . .
 . . 7 | . 1 . | 8 . .
 . 5 . | 3 . 6 | 1 2 .
-------+-------+-------
 . . 9 | . . 5 | . . 4
 . 3 . | . . 8 | . . 6
 . 6 . | . 7 . | 2 . 5



We are in Sudokuland, a place where all the puzzles have one (and only one) solution... but here, this puzzle is not minimal...

Too many data !

As all the puzzles have one (and only one) solution, you can hide the number in r2c9.
Effectively, in r2c9, only the number 1 gives one (and only one) solution to this fantastic puzzle.
The other potential candidate is 2, but it gives me five... solutions

So, in Sudokuland, the puzzles look like :

Code: Select all

 . . . | . . . | . . .
 . . . | . . . | . 7 x
 . . . | . . . | 6 9 8
-------+-------+-------
 . . 4 | . . . | . . .
 . . 7 | . 1 . | 8 . .
 . 5 . | 3 . 6 | 1 2 .
-------+-------+-------
 . . 9 | . . 5 | . . 4
 . 3 . | . . 8 | . . 6
 . 6 . | . 7 . | 2 . 5



But even this one has too many data.
For example you can also hide the number in r5c7 :
If you don't know r2c9 and r5c7, don't worry , the following puzzle :

Code: Select all

 . . . | . . . | . . .
 . . . | . . . | . 7 x
 . . . | . . . | 6 9 8
-------+-------+-------
 . . 4 | . . . | . . .
 . . 7 | . 1 . | x . .
 . 5 . | 3 . 6 | 1 2 .
-------+-------+-------
 . . 9 | . . 5 | . . 4
 . 3 . | . . 8 | . . 6
 . 6 . | . 7 . | 2 . 5



has one (and only one) solution iff r2c9=1 and r5c7=8.

In Sudokuland, a puzzle is minimal if you can not replace any more number by an "x".

Is the last puzzle minimal ?

It's easy to get puzzles with 16 numbers and one "x", using the gfroyle list.
Any puzzles with 15 numbers and 2 "x" ?


JPF

[Ocean]

...In Sudokuland, a puzzle is minimal if you can not replace any more number by an "x".

Is the last puzzle minimal ?

... have no answer for this, but...

It's easy to get puzzles with 16 numbers and one "x", using the gfroyle list.
Any puzzles with 15 numbers and 2 "x" ?

I think the theoretical lowest is placing eight numbers and nine "x" on a board. Any takers for a proof?
Here is an example. I think it has a unique solution. Any solvers?

Code: Select all

 *-----------*
 |...|1..|23.|
 |...|.4.|...|
 |...|567|...|
 |---+---+---|
 |x.x|...|...|
 |x..|...|...|
 |...|..x|.x.|
 |---+---+---|
 |...|...|x.x|
 |xx.|..9|...|
 |...|...|...|
 *-----------*

Your idea reminded me also of another, slightly different idea presented here...

[JPF]

Your idea reminded me also of another, slightly different idea presented here...

Thanks Ocean.
Now, I know where Sudokuland is

As far as my first puzzle (24 clues minimal) is concerned, I tried to substitute a maximum of the given numbers by an "x".
I got this 18 real clues puzzle which has one (and only one solution) :

Code: Select all

 . . . | . . . | . . .
 . . . | . . . | . x 1
 . . . | . . . | x 9 8
-------+-------+-------
 . . x | . . . | . . .
 . . 7 | . x . | 8 . .
 . 5 . | x . 6 | 1 x .
-------+-------+-------
 . . 9 | . . 5 | . . 4
 . 3 . | . . 8 | . . 6
 . 6 . | . 7 . | 2 . 5



but I turned my computer off before the end of the exhaustive search.
It took a while.

I will try to "reduce" it again and will look at your proposed "minimal" puzzle.

What is surprising me, is what it means :
In a puzzle (even "minimal"), there are a lot of redundant information that can be removed and finally get the only one solution.
In particular, the position of a clue is almost as important as the value of the clue itself.

JPF

[Ocean]

Your idea reminded me also of another, slightly different idea presented here...

I solved this one by finding a matching (partial) pattern in gfroyle's list of known 17s. A similar approach can be applied for solving my suggested 'minimal' x-puzzle, and there is only one match.

[JPF]

Here is an example. I think it has a unique solution. Any solvers?

Code: Select all

 *-----------*
 |...|1..|23.|
 |...|.4.|...|
 |...|567|...|
 |---+---+---|
 |x.x|...|...|
 |x..|...|...|
 |...|..x|.x.|
 |---+---+---|
 |...|...|x.x|
 |xx.|..9|...|
 |...|...|...|
 *-----------*

Here, we are

Code: Select all

 5 6 7 | 1 9 8 | 2 3 4
 8 1 9 | 2 4 3 | 6 5 7
 2 4 3 | 5 6 7 | 8 1 9
-------+-------+-------
 4 2 5 | 9 7 1 | 3 6 8
 6 7 8 | 4 3 5 | 9 2 1
 9 3 1 | 6 8 2 | 4 7 5
-------+-------+-------
 7 9 2 | 3 1 4 | 5 8 6
 3 8 6 | 7 5 9 | 1 4 2
 1 5 4 | 8 2 6 | 7 9 3



JPF

[Ocean]

Here, we are

Code: Select all

 5 6 7 | 1 9 8 | 2 3 4
 8 1 9 | 2 4 3 | 6 5 7
 2 4 3 | 5 6 7 | 8 1 9
-------+-------+-------
 4 2 5 | 9 7 1 | 3 6 8
 6 7 8 | 4 3 5 | 9 2 1
 9 3 1 | 6 8 2 | 4 7 5
-------+-------+-------
 7 9 2 | 3 1 4 | 5 8 6
 3 8 6 | 7 5 9 | 1 4 2
 1 5 4 | 8 2 6 | 7 9 3



JPF

Congratulations! Well done. How did you attack the problem? Direct grid search, or pattern match in the list of known 17s?

[tarek]

Would the x positions change if you start from the bottom rather from the top?

I think that you can't have a 15 & 2 xs


but the idea of Absolute minimality (That you could place an x over each digit & still get one result for x) or in other words that you can't achieve a valid puzzle by CHANGING ANY DIGIT is something of a challange


tarek

[JPF]

Here is an example. I think it has a unique solution. Any solvers?

Code: Select all

 P
 . . . | 1 . . | 2 3 .
 . . . | . 4 . | . . .
 . . . | 5 6 7 | . . .
-------+-------+-------
 x . x | . . . | . . .
 x . . | . . . | . . .
 . . . | . . x | . x .
-------+-------+-------
 . . . | . . . | x . x
 x x . | . . 9 | . . .
 . . . | . . . | . . .
 

Congratulations! Well done. How did you attack the problem? Direct grid search, or pattern match in the list of known 17s?

I used a logical approach, with the following technique, well known in Sudokuland, called ZWXZ-fish (from the Ocean)

a 17-clues proper puzzle has a maximum of one 5-clues box and, more precisely, there are only 2 inequivalent puzzles with the box distribution 532221110.

These are :

Code: Select all

S1
 . . . | 2 . . | 4 . .
 . 7 . | . . . | 3 . .
 . 1 . | . . . | . . .
-------+-------+-------
 8 . . | 3 . . | . 2 .
 . . . | . . . | 6 7 .
 . . . | . . . | . 1 5
-------+-------+-------
 4 . . | . 5 1 | . . .
 . . . | . 7 . | . . .
 9 . . | . . . | . . .

and
 

S2
 . . . | 3 . . | 4 . .
 8 . . | 5 . . | . . .
 7 . 6 | . . . | . . .
-------+-------+-------
 . 3 . | . . . | 1 . .
 . . . | . 6 . | . . .
 . . . | . . 8 | . . .
-------+-------+-------
 . . . | 1 5 . | . 7 .
 . . . | . . . | 2 . 9
 . . . | . . . | . 8 6


But the 5-clues boxes of P and S2 are not equivalent.

Code: Select all


     P            S2
 | 1 . . |     | 7 . . |
 | . 4 . |  #  | 2 . 9 |
 | 5 6 7 |     | . 8 6 |
 


Therefore, S2 has to be excluded.


After a -90° rotation, S1 becomes S1* :

Code: Select all

S1*
 . . . | . . 5 | . . .
 . . . | 2 7 1 | . . .
 4 3 . | . 6 . | . . .
-------+-------+-------
 . . . | . . . | 1 . .
 . . . | . . . | 5 7 .
 2 . . | 3 . . | . . .
-------+-------+-------
 . . . | . . . | . . .
 . 7 1 | . . . | . . .
 . . . | 8 . . | 4 . 9


and after some permutations (rows, columns, stacks...), we get the same pattern as P with this puzzle :

Code: Select all

S1**

 . . . | 6 . . | 3 4 .
 . . . | . 5 . | . . .
 . . . | 7 1 2 | . . .
-------+-------+-------
 5 . 7 | . . . | . . .
 1 . . | . . . | . . .
 . . . | . . 3 | . 2 .
-------+-------+-------
 . . . | . . . | 7 . 1
 4 9 . | . . 8 | . . .
 . . . | . . . | . . .
 


which is P after the following relabeling of the digits :
(1,2,3,4,5,6,7,8,9) => (6,7,2,3,4,1,5,9,8)
and we can conclude that P is :

Code: Select all

P
 . . . | 1 . . | 2 3 .
 . . . | . 4 . | . . .
 . . . | 5 6 7 | . . .
-------+-------+-------
 4 . 5 | . . . | . . .
 6 . . | . . . | . . .
 . . . | . . 2 | . 7 .
-------+-------+-------
 . . . | . . . | 5 . 6
 3 8 . | . . 9 | . . .
 . . . | . . . | . . .


The puzzle P is then easy to solve (singles only).

JPF

[JPF]

Would the x positions change if you start from the bottom rather from the top?

Probably yes.
It's what happens for a "normal" non minimal puzzle.

For a "normal" non minimal puzzle P, there are many ways to remove one or more clues to make it minimal.
In addition, if n(P) is the number of clues of P, you can have P1<P and P2<P, with
P1 and P2 minimal puzzles and n(P1)<n(P2)<n(P).

I think, it's probably be the same thing for the x-minimality…

I think that you can't have a 15 & 2 xs

That's not exactly true :
For example, in the Ocean's problem the following (15 & 2x) puzzle has one and only one solution :

Code: Select all

 . . . | 1 . . | 2 3 .
 . . . | . 4 . | . . .
 . . . | 5 6 7 | . . .
-------+-------+-------
 4 . 5 | . . . | . . .
 6 . . | . . . | . . .
 . . . | . . 2 | . 7 .
-------+-------+-------
 . . . | . . . | 5 . 6
 x x . | . . 9 | . . .
 . . . | . . . | . . .



Obviously it is not an x-minimal puzzle.

but, if your question is : can we have a x-minimal (15 & 2x) puzzle ...
my answer is : I don't know

JPF

[Ocean]

I used a logical approach, ...

Good explanation of the logic. I used the same technique when creating the x-puzzle, albeit in opposite direction. First, selected a known 17 with a unique pattern. Then choosing some permutation and relabelling (instead of finding them).

[Of course, there might be other non-equivalent 17s with equivalent pattern lurking around, but the probability is very small. So I think the given x-puzzle has a unique solution. Verifying the uniqueness would prove existence of unique (8 & 9x) puzzles. X-puzzles with less than 8 digits can never be unique, because if a solution exists, there will also be another with swapped digits.]

[Smythe Dakota]

Even those who advocate the use of uniqueness techniques to solve ordinary puzzles would, I think, wince at the idea that the ONLY legal solutions are those which do not yield other side-solutions.

For example, if you have a puzzle where r3c2 is blank initially, and where a 4 in that cell would yield a unique solution, whereas a 7 would yield five solutions, is it fair to demand that a 4 be placed there?

This Sudokuland is a strange place.

Bill Smythe

[JPF]

Is it not also true (at least with Pappocom-published puzzles) that minimality (non-redundancy of the clue set) ia assured? If so, how do you feel about using THAT fact to help solve a puzzle?

Bill Smythe

Here is one non minimal puzzle from Sudokuland.
Any solvers ?

Code: Select all

 x x 6 | . . . | . . .
 . x . | . . . | 4 . .
 . . . | . . . | . . x
-------+-------+-------
 . . . | x . . | . . .
 . . . | x . x | . . .
 . . . | 9 . . | . x 1
-------+-------+-------
 x . . | . . . | 8 . .
 5 . . | . x . | . . .
 . . . | . 2 . | . 3 .



This Sudokuland is a strange place.

JPF

[ab]

Is it not also true (at least with Pappocom-published puzzles) that minimality (non-redundancy of the clue set) ia assured? If so, how do you feel about using THAT fact to help solve a puzzle?

Bill Smythe

Pappocom puzzles are not all minimal. Most of the Times Superior puzzles are not minimal.
Here's Times Superior #20:

Code: Select all

5..|1.2|..9
...|.8.|...
..1|7.9|6..
-----------
65.|...|.18
8..|...|..3
14.|...|.72
-----------
..8|4.7|3..
...|.1.|...
2..|3.8|..4


It can be solved with a hidden triple.

However remove r6c1 and r4c9 and you get this:

Code: Select all

5..|1.2|..9
...|.8.|...
..1|7.9|6..
-----------
65.|...|.1.
8..|...|..3
.4.|...|.72
-----------
..8|4.7|3..
...|.1.|...
2..|3.8|..4


Now you also need a hidden pair and locked candidates.

You can remove three clues from Times Superior #29 to get a symmetric puzzle needing a swordfish.

Having said all that I don't think it's important for puzzles to be minimal. To be symmetric minimal is more important in my view.
Arguably Times Superior puzzles #20 and #29 are symmetrically minimal if you take their symmetry group to be one containing two reflections and one rotation.

[Ocean]

Here is one non minimal puzzle from Sudokuland.
Any solvers ?

Code: Select all

 x x 6 | . . . | . . .
 . x . | . . . | 4 . .
 . . . | . . . | . . x
-------+-------+-------
 . . . | x . . | . . .
 . . . | x . x | . . .
 . . . | 9 . . | . x 1
-------+-------+-------
 x . . | . . . | 8 . .
 5 . . | . x . | . . .
 . . . | . 2 . | . 3 .



JPF

Nice puzzle. Proposed solution (tiny letters, in case in case somebody else wants to try):

976|...|...
.2.|...|4..
...|...|..5
---+---+---
...|4..|...
...|8.5|...
...|9..|.71
---+---+---
4..|...|8..
5..|.1.|...
...|.2.|.3.