The New Sudoku Players' Forum

[ixsetf]

Has anyone thought to do this? The same techniques can be used to eliminate candidates from invalid puzzles as valid puzzles, and while its clearly impossible to remove all candidates from an invalid grid, there are a fixed number of possible candidates which can occupy any given cell. One could potentially grade an invalid puzzle based on the difficulty of techniques required to reach this final state.

This raises the question, what is the highest potential difficulty for an invalid grid? And is on average higher or lower than that of a valid grid?

[champagne]

Has anyone thought to do this? The same techniques can be used to eliminate candidates from invalid puzzles as valid puzzles, and while its clearly impossible to remove all candidates from an invalid grid, there are a fixed number of possible candidates which can occupy any given cell. One could potentially grade an invalid puzzle based on the difficulty of techniques required to reach this final state.

This raises the question, what is the highest potential difficulty for an invalid grid? And is on average higher or lower than that of a valid grid?

I try a quick answer.

Just assume that your puzzle has only 2 solutions due to a UR not solved through a given. Then, you can face very similar difficulties as in any other valid puzzle.

You have several other problems with puzzles having multiples solutions:
a) using rules based on uniqueness, you can come to a false result (you are not authorized to use such rules unless you know that you have a valid puzzle)
b) in most case, you'll try without any success the most difficult rules you have in your basket.

That's why I never try to solve with "nice rules" a puzzle without having applied the brute force to check that the puzzle is valid.

[dobrichev]

It is interesting.

First, more specific definition of "invalid puzzle" is needed. There are puzzles which can be completed to more than one solutions and puzzles which can't be completed at all. Puzzles from both categories can have or not redundant givens.
Second, some modifications on the popular grading rules must be done. One example is the removal of the techniques which expect uniqueness.
It could be possible with similar grading rules modifications to try also the pencilmarks-only puzzles - those with only pencilmarks initially defined, possibly with zero "givens".

As for the average difficulty I expect the vast majority of the invalid puzzles are easy to detect as invalids simply because there are too many ways to compose an invalid puzzle with duplicates in a houses.

[ixsetf]

I try a quick answer.

Just assume that your puzzle has only 2 solutions due to a UR not solved through a given. Then, you can face very similar difficulties as in any other valid puzzle.

You have several other problems with puzzles having multiples solutions:
a) using rules based on uniqueness, you can come to a false result (you are not authorized to use such rules unless you know that you have a valid puzzle)
b) in most case, you'll try without any success the most difficult rules you have in your basket.

That's why I never try to solve with "nice rules" a puzzle without having applied the brute force to check that the puzzle is valid.

It is true that rules based on uniqueness can not be used with an invalid puzzle, and a solver would have to be modified in such a way to not use them when grading invalid puzzles.

Maybe it would be better if I gave an example.

Take for example this puzzle

Code: Select all

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

300700400020080050001009006700400100080000020009006003400100700050020080006003009


There are 8 possible solutions to this puzzle, they are listed below.

Hidden Text: Show

365712498927684351841359276732498165684531927519276843498165732153927684276843519
365712498927684351841539276732498165684351927519276843498165732153927684276843519
368715492927684351541239876735492168684351927219876543492168735153927684876543219
368751492927684351541239876735492168684315927219876543492168735153927684876543219
395762418624381957871549236762438195183957624549216873438195762957624381216873549
395762418624381957871549236762438195583917624149256873438195762957624381216873549
398765412624381957571249836763452198185937624249816573432198765957624381816573249
398765412624381957571249836765432198183957624249816573432198765957624381816573249

We can create a pencilmarked 'solution' grid by comparing these.

In all solutions, we see that r1c2 is either a 6 or a 9, therefore we can write 69 into r2c2 of our solution grid. For r1c3 all solutions result in either a 5 or an 8, therefore for that cell we can write in 58. If we repeat this process for all cells in the grid, we arrive at the following.

Hidden Text: Show

Code: Select all

+--------------+--------------+--------------+
|    3  69  58 |    7 156 125 |    4  19  28 |
|   69   2  47 |   36   8  14 |   39   5  17 |
|   58  47   1 |  235 345   9 |   28  37   6 |
+--------------+--------------+--------------+
|    7  36 235 |    4 359  28 |    1  69  58 |
|  156   8 345 |  359 135 157 |   69   2  47 |
|  125  14   9 |   28 157   6 |   58  47   3 |
+--------------+--------------+--------------+
|    4  39  28 |    1  69  58 |    7  36  25 |
|   19   5  37 |   69   2  47 |   36   8  14 |
|   28  17   6 |   58  47   3 |   25  14   9 |
+--------------+--------------+--------------+

As the puzzle has multiple solutions we would not be able to determine a value for all cells using valid logical techniques, however we can remove candidates. A simple sweep produces the following grid.

Hidden Text: Show

Code: Select all

+--------------+----------------+--------------+
|    3  69  58 |    7   156 125 |    4  19 128 |
|   69   2  47 |   36     8  14 |   39   5  17 |
|   58  47   1 |  235   345   9 |  238  37   6 |
+--------------+----------------+--------------+
|    7  36 235 |    4   359 258 |    1  69  58 |
|  156   8 345 |  359 13579 157 |  569   2 457 |
|  125  14   9 |  258   157   6 |   58  47   3 |
+--------------+----------------+--------------+
|    4  39 238 |    1   569  58 |    7  36  25 |
|   19   5  37 |   69     2  47 |   36   8  14 |
|  128  17   6 |   58   457   3 |   25  14   9 |
+--------------+----------------+--------------+

There are a number of differences between this and our 'solution' grid above, so we continue to remove candidates. We see that it is possible eliminate 5 from r5c79, through a naked pair with 58 r4c9 and r6c7, as well as eliminating 5 from r79c5 with the naked pair at r9c4 and r6c7.

After a number of other basics we arrive at the following.

Hidden Text: Show

Code: Select all

+--------------+----------------+--------------+
|    3  69  58 |    7   156 125 |    4  19  28 |
|   69   2  47 |   36     8  14 |   39   5  17 |
|   58  47   1 |  235   345   9 |   28  37   6 |
+--------------+----------------+--------------+
|    7  36 235 |    4   359  28 |    1  69  58 |
|  156   8 345 |  359 13579 157 |   69   2  47 |
|  125  14   9 |   28   157   6 |   58  47   3 |
+--------------+----------------+--------------+
|    4  39  28 |    1    69  58 |    7  36  25 |
|   19   5  37 |   69     2  47 |   36   8  14 |
|   28  17   6 |   58    47   3 |   25  14   9 |
+--------------+----------------+--------------+

We can then use some simple coloring to eliminate the final candidates

Hidden Text: Show

Code: Select all

+--------------+--------------+--------------+
|    3  69  58 |    7 156 125 |    4  19  28 |
|   69   2  47 |   36   8  14 |   39   5  17 |
|   58  47   1 |  235 345   9 |   28  37   6 |
+--------------+--------------+--------------+
|    7  36 235 |    4 359  28 |    1  69  58 |
|  156   8 345 |  359 135 157 |   69   2  47 |
|  125  14   9 |   28 157   6 |   58  47   3 |
+--------------+--------------+--------------+
|    4  39  28 |    1  69  58 |    7  36  25 |
|   19   5  37 |   69   2  47 |   36   8  14 |
|   28  17   6 |   58  47   3 |   25  14   9 |
+--------------+--------------+--------------+

As this is equivalent to our 'solution' grid, we may now stop. We may then rate the puzzle based on the solution path used.

This of course would only work for puzzles with multiple solutions, but for those with no solutions grading could be done on the path up to the first contradiction (first empty cell).

[JPF]

You can use for instance Sudoku Explainer: the rating is 3.8
First, disable BUG and UR/loop in Options/Solving Techniques and then use the program step by step until you get the message "This Sudoku is not valid".
The rating is the maximum value of the techniques used on the path.

The final map of candidates looks like:

Explainer.jpg (44.44 KiB) Viewed 1663 times

JPF

[ixsetf]

You can use for instance Sudoku Explainer: the rating is 3.8
First, disable BUG and UR/loop in Options/Solving Techniques and then use the program step by step until you get the message "This Sudoku is not valid".
The rating is the maximum value of the techniques used on the path.
JPF

While SE worked in this case, there are many situations where it will not. Sudoku explainer will display "This Sudoku is not valid" when it can no longer make progress with basic techniques. It will not display the correct rating if it requires higher level loops.

For example the following,

Hidden Text: Show

Screenshot 2014-11-03 18.25.07.png (42.85 KiB) Viewed 1650 times

It has the following solutions,

Hidden Text: Show

Code: Select all

362159487719684235854732916127498653486513729935276148273861594648925371591347862
362519487719684235854732916127498653486153729935276148273861594648925371591347862
372569418516284739894713256167452893483197625925836147239671584648925371751348962
372569418615284739894713256157492683486137925923856147238971564549628371761345892
375269418612584739894713256157492683486137925923856147238971564549628371761345892
376259481219684735854713296167492853483175629925836147732941568691528374548367912

If you examine the solutions for r8c1, you will see that the only possibilities are 5 and 6. However, SE stops with 1, 4, 5, 6, and 8 as possibilities. It isn't that its impossible to make progress with logical techniques either, as the following loop can remove the 1.

Hidden Text: Show

X-CYCLE on 1 (Grouped Discontinuous Alternating Nice Loop, length 8):
+1[H1]-1[H9]+1[J8]-1[C8]+1[C5]-1[D5]+1[D1]-1[H1]
- Contradiction: When H1 is set to 1 the chain implies it cannot be 1 - it can be removed

[JPF]

well, if you gently use explainer, pushing alternatively the buttons Get next Hint and Solve Step, you get (after a while):

Explainer-2.jpg (43.71 KiB) Viewed 1643 times

note that r2c8 has only one candidate = 3, which is expected.

JPF

[ixsetf]

well, if you gently use explainer, pushing alternatively the buttons Get next Hint and Solve Step, you get (after a while):

note that r2c8 has only one candidate = 3, which is expected.

JPF

I'm guessing this is a difference in versions since that was the process I was using.

[m_b_metcalf]

This of course would only work for puzzles with multiple solutions, but for those with no solutions grading could be done on the path up to the first contradiction (first empty cell).

For your consideration, here are three puzzles of different levels of 'difficulty', each with zero solutions.

Regards,

Mike Metcalf

Code: Select all

 1 2 . . 3 . . 4 .
 5 . . . . 1 3 . .
 . . . 2 . . 5 . .
 . . 4 6 . . . 7 .
 8 . . . . 9 2 . .
 . 5 . . 4 . . . 6
 . 7 8 . 6 . . . .
 3 . . 8 . . . . .
 . . . . . 3 . . 4   'easy'

 1 2 . . 3 . . 4 .
 5 . . . . 1 3 . .
 . . . 2 . . 5 . .
 . . 4 6 . . . 5 .
 7 . . . . 8 2 . .
 . 5 . . 4 . . . 6
 . 9 7 . 6 . . . .
 3 . . 7 . . . . .
 . . . . . 3 . . 4   'hard'

 1 2 . . 3 . . 4 .
 5 . . . . 6 7 . .
 . . . 2 . . 8 . .
 . . 4 5 . . . 1 .
 3 . . . . 8 5 . .
 . 5 . . 2 . . . 7
 . 9 3 . 6 . . . .
 7 . . 3 . . . . .
 . . . . . 9 . . 1   'very hard'


[m_b_metcalf]

for those with no solutions grading could be done on the path up to the first contradiction (first empty cell).

Note that as well as there being an empty cell, other causes for zero solutions are:

a row/column/box not having at least 1 candidate for each unsolved value;

a clash: two (or more) single candidate values share the same cell.

Regards,

Mike Metcalf

[ixsetf]

for those with no solutions grading could be done on the path up to the first contradiction (first empty cell).

Note that as well as there being an empty cell, other causes for zero solutions are:

a row/column/box not having at least 1 candidate for each unsolved value;

a clash: two (or more) single candidate values share the same cell.

Regards,

Mike Metcalf

Can you give an example of when having a row/column/box without 1 candidate per cell wouldn't lead to an empty cell, and when a clash would be possible to create without taking multiple steps at once? I can't think of a scenario where this would occur.

Also while I think I've figured out how to make JPF's method work, I've hit a snag with the following puzzle. After two steps, far before it should actually stop, SE only gives "more than one solution" as a step.

Code: Select all

1....9...
.3..8....
..47.....
..74....3
.8..7..2.
9....51..
.....19..
....2..8.
...3....4

[JPF]

Also while I think I've figured out how to make JPF's method work, I've hit a snag with the following puzzle. After two steps, far before it should actually stop, SE only gives "more than one solution" as a step.

Code: Select all

1....9...
.3..8....
..47.....
..74....3
.8..7..2.
9....51..
.....19..
....2..8.
...3....4

Here is the final explainer grid:

Explainer 2.jpg (69.6 KiB) Viewed 1579 times

Clue: ignore the Naked Pair in B5 until the end.

Note that explainer has a hard time eliminating some candidates. Example:

Explainer 3.jpg (65.13 KiB) Viewed 1579 times

JPF

[ixsetf]

Ok, so I figure the differnce between what we are doing has to do with which of the two steps we start with. I assume you start with apply next step, rather than get next hint. There are certain problems with begining with apply next step, as the first step will not be applied until a more simple step is made available. To illustrate this, in the grid above there is a naked pair at r5c6 and r6c5, this should have removed the 6s at r4c56 and r56c4 before SE attempted to use the chain which was posted. It seems likely that this increased the difficulty of the steps necessary to solve the puzzle.

[JPF]

For some reason, explainer checks the validity of the puzzle when its proposed hint is naked pair in B5 (r5c6=36 and r6c5=36) and when we use solve step after this hint.
To avoid the crash, I have never used the button solve step after this hint.
As a consequence, 6 is never eliminated as a candidate in r4c56, r5c4 and r6c4.
Therefore, you are right: explainer is forced to use (too) sophisticated techniques to eliminate candidates in the grid.

JPF

[m_b_metcalf]

Can you give an example of when having a row/column/box without 1 candidate per cell wouldn't lead to an empty cell,

This is not what I said. I mean that, for example, if a row doesn't contain a clue with the value '6', then it must contain at least one candidate with that value.

The posted examples exhibit this feature at some point along their 'solution' paths. In puzzle generation this is one of the checks that helps to avoid making unneccessary calls to a brute-force solver.

and when a clash would be possible to create without taking multiple steps at once? I can't think of a scenario where this would occur.

That's right.

Regards,

Mike Metcalf