Minimal puzzles in Sudokuland

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

Minimal puzzles in Sudokuland

Postby JPF » Fri Apr 28, 2006 12:53 am

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
Last edited by JPF on Fri Apr 28, 2006 5:34 am, edited 1 time in total.
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Re: Minimal puzzles in Sudokuland

Postby Ocean » Fri Apr 28, 2006 1:49 am

JPF wrote:...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...
JPF wrote: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...
Ocean
 
Posts: 442
Joined: 29 August 2005

Re: Minimal puzzles in Sudokuland

Postby JPF » Sat Apr 29, 2006 7:03 am

Ocean wrote: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
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Re: Minimal puzzles in Sudokuland

Postby Ocean » Tue May 02, 2006 4:33 pm

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.
Ocean
 
Posts: 442
Joined: 29 August 2005

Re: Minimal puzzles in Sudokuland

Postby JPF » Wed May 03, 2006 12:35 am

Ocean wrote: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
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Re: Minimal puzzles in Sudokuland

Postby Ocean » Wed May 03, 2006 5:14 am

JPF wrote: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?
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby tarek » Wed May 03, 2006 6:14 am

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:D


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

Re: Minimal puzzles in Sudokuland

Postby JPF » Thu May 04, 2006 5:08 pm

Ocean wrote: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 | . . .
 . . . | . . . | . . .
 


Ocean wrote: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):D

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
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby JPF » Thu May 04, 2006 10:01 pm

tarek wrote: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…

tarek wrote: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
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Re: Minimal puzzles in Sudokuland

Postby Ocean » Thu May 04, 2006 10:20 pm

JPF wrote: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.]
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Smythe Dakota » Sat May 06, 2006 6:56 pm

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
Smythe Dakota
 
Posts: 552
Joined: 11 February 2006

Postby JPF » Tue May 16, 2006 4:13 pm

Smythe Dakota wrote: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 .


Smythe Dakota wrote:This Sudokuland is a strange place.

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

Postby ab » Tue May 16, 2006 5:10 pm

JPF wrote:
Smythe Dakota wrote: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

Smythe Dakota wrote:


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.
ab
 
Posts: 451
Joined: 06 September 2005

Postby Ocean » Thu May 25, 2006 7:12 pm

JPF wrote: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.
Ocean
 
Posts: 442
Joined: 29 August 2005


Return to General

cron