The New Sudoku Players' Forum

[kwdos]

The theoretical acceptability or otherwise of forced chains has been discussed exhaustively here (and elsewhere) and I have no wish to reopen old issues (personally I think the technique is clever, ingenious and elegant, but as many have observed these assessments are in the eye of the beholder).

However, now I have started to use the technique, I do have one worry. What if one applies the technique to incorrectly set Sudokus which have multiple solutions? Is there a danger that one might 'crystallise' one of the solutions by selecting a particular forced chain from among the many possibilities which sometimes arise (another possible chain might have 'crystallised' another solution) and thus miss the fact that multiple solutions exist?

I know that such incorrectly set Sudokus are very rare but, even if they only occur as a theoretical possibility, they seem to raise the possibility that use of forced chains implicitly assumes the existence of just one solution. I have not found any case where this possibility definitely arises (not that I have searched much yet) and it may be that there is some reason(s) why this worry can be quashed and I would be delighted if anyone can remove my worry!

[stuartn]

I think we may have looked at this before - IMHO (and I'm sure tso will correct me if I'm wrong), to use the assumption that a grid is unique cannot be a valid method of elimination - because if you reach the stage where such a technique has to be used, the grid has multiple solutions anyway....

There are plenty of sites out there providing 'invalid' Sudoku's (they're still number grid puzzles - but they're not Sudoku's) - Pappocoms et al are certainly the most reliable for unique grids

stuartn

[kwdos]

Stuartn comments that 'to use the assumption that a grid is unique cannot be a valid method of elimination'. This is precisely my point. It looks as if forcing chains may be implicitly making this assumption - and, if so, then the technique must certainly be called into question!

[Karyobin]

!

Goodness.

[stuartn]

kwdos wrote:

It looks as if forcing chains may be implicitly making this assumption

Disagree entirely - you can use forcing chains on the simplest of unique Sudoku's - and not use another technique whatsoever to finish the grid. It is also useful on the most difficult - as a recent thread showed. - but it's certainly not making any assumptions about uniqueness. Can you tell us more about why you reckon they implicitly make the assumption?

stuartn

[kwdos]

I thought that my first message did so - I'm sorry if I'm failing to make the point very well.

If one has an incorrectly set Sudoku and uses a forcing chain my worry is that this will pick out just one of the possible solutions, thus hiding the existence of others. As I said in the first message, I don't know if this could ever happen, but I can't see any reason why it could not. I was hoping that one of the experts like Tso could lay my worry to rest!

[tso]

Forcing chains do not require the puzzle to have a unique solution any more or any less than naked singles. They work exactly as well in a puzzle that has multiple solutions, regardless of whether or not the solver knows it has multiple solutions. It even works in a puzzle with NO solution.

Here is a simple example of a forcing chain:

Code: Select all

Row 3 -- [??][??][12][13]
Row 4 -- [??][??][23][34]


r3c3=1 => r3c4=3 => r4c4=4
r3c3=2 => r4c3=3 => r4c4=4
Therefore, r4c4=4


If all we know about this puzzle is the possibilities remaining in these four cells, we KNOW, by forcing chains, that the [34] cell CANNOT contain a 3 without contradiction. We may later discover that the puzzle has 1000 solutions or none at all -- regardless -- THIS cannot be '3'.

[tso]

The following puzzle from this thread has exactly two solutions:

Code: Select all

1.....58.
8....1..6
.6..2....
...59....
....7....
.93..2...
.1....8.4
...9.7.5.
6..2..71.


You may use any tactic to try to find the two solutions, including forcing chains. The only thing that will be of less use if it were to come up is the "uniqueness test" -- which IS a perfectly valid tactic to eliminate a possibility if one knows the solution is unique.


It would be interested to see if Sudokus could be created in which the uniquess test is the simplest path to the solution.

By the way, sometimes a particular situation is given less of a spotlight because of it is perceived to be 'rare'. If a generator, human or otherwise, intentionally creates puzzles with whatever structure, either creating them from scratch or simply making lots of puzzles and filtering for the wanted tactic -- the relative infrequency becomes meaningless.

[kwdos]

Thanks for your comments, Tso.

Of course in most (and quite likely all) situations forcing chains undeniably give the correct solution - certainly in all cases where the Sudoku is correctly set. I just wonder whether, even in principle in a multi-solution Sudoku (i.e. an incorrectly set non-valid Sudoku), from among many complex forcing chains which could perhaps occur simultaneously, there might exist cases where one forcing chain leads to an apparently correct result for one of the many solutions whereas if one picked another forcing chain one might produce one of the other solutions. If that were to be true then obviously one would need some other test to check that the Sudoku one thinks one has solved using forcing chains really has a unique solution and one could not necessarily trust such a solution without making an assumption about uniqueness. I see that I explained this badly originally but I hope this has made my niggling worry clearer.

I know you believe forcing chains can't hide the non-uniqueness of a multi-solution Sudoku - indeed I suspect, and hope, that they cannot - but I'd just like to see a rigourous proof of this!

[stuartn]

tso wrote;

The only thing that will be of less use if it were to come up is the "uniqueness test" -- which IS a perfectly valid tactic to eliminate a possibility if one knows the solution is unique.

Mmmmm... and your proof?... if a solution is unique surely you should never have to use this technique.... unless you're looking for a specific grid within a multiplicity of answers.

I await your proof with interest......

stuart

[Lummox JR]

Inasmuch as one of the constraints in valid sudoku is uniqueness of solution, I don't see the problem anyway. It's as valid to assume the grid has a unique solution as it is to assume the creator didn't screw it up by putting two 5's in the wrong column. Any test that relies on uniqueness, however, doesn't stand to crystalize the solution but to turn a multiple-solution grid into an insoluble one--and either is equally invalid.

In the case of forcing chains, I really don't see this causing any reduction of multiple solutions. If the logic rules in the chain apply at all, they apply to all of the potential solutions. But then, if you're trying this on a multiple-solution grid then you're already fighting a losing battle.

[tso]

tso wrote;

The only thing that will be of less use if it were to come up is the "uniqueness test" -- which IS a perfectly valid tactic to eliminate a possibility if one knows the solution is unique.

Mmmmm... and your proof?... if a solution is unique surely you should never have to use this technique.... unless you're looking for a specific grid within a multiplicity of answers.

I await your proof with interest......

stuart

I didn't imply the existance of a particular Sudoku in which the solver MUST use this tactic, or even that there exists one in which this tactic would be the simplest route to the solution, only that it is a valid tactic.

IF a puzzle has a unique solution, and IF a particular placement will leave an ambiguous situation, then that placement can be eliminated.

If a puzzle has mulitple soutions, we cannot always make that statement.

This tactic is more common in other types of logic puzzles. It comes up quite often in Battleship puzzles, and there has been disagreement on whether or not it is "fair" -- whatever that means -- to use (see "uniqueness assumption"". In other puzzles, like Dominosa, it comes up in nearly every puzzle and is usually the most directy route to the answer. Of course, all these puzzles are solvable without this tactic, just as all Sudoku are solvable without using naked pairs -- or naked singles for that matter.

Without listing them, I've used the uniqueness test in many other Nikoli puzzles and "nikoli-type" puzzles.

[tso]

... I just wonder whether, even in principle in a multi-solution Sudoku (i.e. an incorrectly set non-valid Sudoku), from among many complex forcing chains which could perhaps occur simultaneously, there might exist cases where one forcing chain leads to an apparently correct result for one of the many solutions whereas if one picked another forcing chain one might produce one of the other solutions.

No. All logical steps end at some point when there are dual solutions. If there are mutiple solutions, there will come a point there there simply is no logic reason to pick one path over another. You simple cannot have two valid forcing chains that give contraditory results -- which is what is required for them to lead to two different solutions. Take for example, this very simple puzzle, a 2x2 Latin Square:

Code: Select all

. .
. .


Fill in the cells with the digits "1" or "2" so no digit appears twice in each column and row.

There are two solutions. There is no way around this -- there is no "better" or "right" solution.

Code: Select all

1 2
2 1

and

2 1
1 2

No "logical" step will favor one over the other. Logic will enable you to narrow your search down to two answers. There is no "there" there.

... If that were to be true then obviously one would need some other test to check that the Sudoku one thinks one has solved using forcing chains really has a unique solution and one could not necessarily trust such a solution without making an assumption about uniqueness. I see that I explained this badly originally but I hope this has made my niggling worry clearer.

If the puzzle has more than one solution, the solver will NEVER find a SINGLE solution using forcing chains, swordfish, etc, as demonstrated above.

I know you believe forcing chains can't hide the non-uniqueness of a multi-solution Sudoku - indeed I suspect, and hope, that they cannot - but I'd just like to see a rigourous proof of this!

The micro-mini example should stand instead of a proof.


Using the dual-solution puzzle posted further up in this thread:

Code: Select all

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


Using relatively simple logic, I come to:

Code: Select all

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



{1}     {237}   {2479}  {3467}  {346}   {3469}  {5}     {8}     {279}   
{8}     {2357}  {24579} {347}   {345}   {1}     {2349}  {23479} {6}     
{3579}  {6}     {4579}  {3478}  {2}     {34589} {1349}  {3479}  {179}   
{247}   {2478}  {16}    {5}     {9}     {3468}  {1234}  {23467} {1278} 
{245}   {2458}  {16}    {13468} {7}     {3468}  {12349} {23469} {12589}
{457}   {9}     {3}     {1468}  {468}   {2}     {14}    {467}   {1578} 
{279}   {1}     {279}   {36}    {356}   {356}   {8}     {29}    {4}     
{234}   {234}   {8}     {9}     {1}     {7}     {6}     {5}     {23}   
{6}     {35}    {59}    {2}     {48}    {48}    {7}     {1}     {39}   

For no logical reason, I can place a '3' in r9c2, leading easily to one of the two solutions:

Code: Select all

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


If instead, I place a 5 in r9c2, with great difficulty, including forcing chains, I come up with the one and only other solution:

Code: Select all

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


Forcing chains and all other logical tactics can only give the solver the value of the cells that are the same in both solutions, or eliminate possiblities that can be removed from both solutions, nothing further. Unless the solver makes an unsupported assumption, as I did by placing a digit in r9c2, the solving process comes to a dead end.

If whoever or whatever posed the puzzle had only one of the solutions in mind -- claiming for no good reason that this was the "correct" soluton and the other was not -- well, what exactly does that mean? Where reduced to guessing how many fingers they're holding up behind they're back.

[kwdos]

Oh dear, I see that I have still not made the situation that bothers me clear. I have been trying not to be too wordy, but I will abandon that strategy and I will try to spell out more precisely the type of situation that bothers me. [ Note that I am not saying that there is definitely a real issue to be addressed here in the case of multi-solution Sudokus and I am quite sure that there is no issue with correctly set Sudokus. Nor am I suggesting that I have any proof or example of where there is a problem: rather I am saying that i'm not yet totally convinced that there is not an issue to be addressed. Note also that my apparent problem may well go away for me when I have a better feel for the use of forcing chains : nevertheless, I will have one last go at trying to clarify the issue. With respect to the poster who suggested that it is in any case reasonable to assume that a given Sudoku will just have one solution, I know some people are happy to do that, but I set Sudokus myself occasionally for friends and family and, at least for problem-setters, it is absolutely vital that any techniques one uses are 'guaranteed' to spot multiple solutions. ]

Consider xy-chains. One starts at a particular cell with two candidates - one of which will be correct and one false, but initially at least one does not know which is which -
and follows a 2-branched chain or possibly multiple chains from this cell and tries to find common end-points. Provided one is working within a correctly set Sudoku, the logic is
then absolutely clear and any cells found to have a unique value must be correct.

Now consider an incorrectly set Sudoku. This will have some regions with uniquely-valued cells - and if the forcing chains go via these cells then again any conclusions
to be made by following these chains must be right. There will however also be regions of the incorrectly set Sudoku within which multiple solutions are possible and where, as a result, both candidates in any cell with two possible values are simultaneously right and wrong (i.e. they will be right in one solution and wrong in another solution). Now the consequences of following xy-chains don't seem quite so clear to me and I just wonder whether there could ever be situations where multiple forcing chains exist in this region of the Sudoku whereby one or more chain might resolve into just one of the solutions
- presumably another chain could then resolve into the other solution(s).

It may be that one could never get forcing chainswhich resolve within a non-uniquely valued part of any incorrectly set Sudoku - I am just not sure about this - though clearly, if resolvable forcing chains cannot exist within such regions, then there would be no problem.

I have clearly made a mess of explaining this and I do apologize for wasting people's time up to this point!

[stuartn]

I've just finished writing a prog that finds these chains and your point is quite right.... there ARE chains that will confirm a placement (ie - all possible starting elements result in the same result for a cell) but which later prove to be invalid. On further inspection there are always other linked chains which lead to inconsistencies further down the line.

stuartn