SuDoku question

I am just curious if anyone knows whether or not bifurcation or the "brute force" method is sometimes absolutely necessary to solve one of the tougher Sudoku

For those of you who don't know bifurcation refers to when you try out each possibility for a locatio for which it could be a limited number of options (usually only 2), and then eliminate the one which leads to a contradiction. It is a last-resort method of sorts.

Several of the harder sudoku seem to require use of this technique, because I have found myself unable to discern or eliminate any of the remaining options using any other method.

This one for instance..

~~6~~~~~~
84~3~2~~~
32~~~5~74
~6~~9~8~~
~~~624~~~
~~2~3~~6~
21~9~~~87
~~~4~3~25
~~~~~~1~~

I managed to get it this far without brute force/guessing.

~~6~49238
84~3~25~~
32~~~5~74
463~9~8~2
~~~6247~3
~~2~3~46~
214956387
~~~413~25
~352~~14~

Any other super-advanced techniques or logic which could proceed forward from this point?

There is also the question of defining exactly when something is bifurcation and when it is not. If you can see forward to the contradiction in your head does it still count? Is a three step contradiction, for example, still included here?

Originally posted by droflace
There is also the question of defining exactly when something is bifurcation and when it is not. If you can see forward to the contradiction in your head does it still count? Is a three step contradiction, for example, still included here?

If I can see the contradiction before I begin putting in the wrong numbers, then I would find that acceptable and more satisfying than if I start filling in the numbers and find the contradiction after the fact.

My problem with this one is that looking back after solving it, I can't find the reason for the contradiction the other way, the "why-it-has-to-be" if you will.

EDIT: Anyone know how to to do a fixed spacing font on here? It would make ASCII pictures and diagrams so much easier..

Any other super-advanced techniques or logic which could proceed forward from this point?

you can show, that in row 2 column 8 is a 1.
There are only 1 and 9 possible and you can exclude the 9 with bifucation.
The rest is easy. To see the bifucation trick, you have to eliminate a lot
of candidates, first.

I don't know, whether there exists sudokus, which only can be solved with
brute force. I have heard about a list of extreme hard, not yet solved (without
brute force, of course ) sudokus in the net.

Originally posted by afx
you can show, that in row 2 column 8 is a 1.
There are only 1 and 9 possible and you can exclude the 9 with bifucation.
The rest is easy. To see the bifucation trick, you have to eliminate a lot
of candidates, first.

I don't know, whether there exists sudokus, which only can be solved with
brute force. I have heard about a list of extreme hard, not yet solved (without
brute force, of course ) sudokus in the net.

"Unsolveables" is the term the site uses, if you're talking about the one I'm thinking about.

They are called that because they seem to resist every other known technique of solving them. Bifurcation or "brute force" isn't particularly efficient, but it always works on a legitimate sudoku given you apply it deep enough.

I did examine the above problem by examining strongly linked squares, and I have eliminated one of three answers on three different squares.

Row 2, Column 9 can't be 9, and is either 6 or 1.
Row 5, Column 3 can't be 9, and is either 8 or 1.
Row 5, Column 8 can't be 1, and is either 9 or 5.

(Strongly linked refers to two or more squares with an "either-or" relationship. With the above three above eliminations, they can't be the first value because they are in line with 2 other squares which are indirectly, but still strongly, linked. One or the other is the eliminated number, although you don't know which one for the moment.)

EDIT: Oops, Row 5, Column 3 is aligned with 2 directly strongly linked spots.. I should have seen that one easier..

I think I may have discovered a good rule to use, although I still don't quite understand why..

Suppose I have in a particular element (row, column, or box), I have 6 numbers entered in already, and only A, B, and C left to place. I have eliminated A from one location, and B from another, but have one spot left that could be A, B, or C. (So I have BC, AC, and ABC.)

It would seem that I might be able to eliminate C from the ABC spot. What I don't know is why this works (and indeed I'm not yet positive it does work. For all I know, it might just be that odds favor it, but don't guarantee it.)

Row 2, Column 9 can't be 9, and is either 6 or 1.
Row 5, Column 3 can't be 9, and is either 8 or 1.
Row 5, Column 8 can't be 1, and is either 9 or 5.

you got these 3 exlusions, because you looked at the
cells with only to possible values.
you get an alternative strong link looking for digits
only allowed in to places of a row/col/box:
r2c8=9=r5c8=5=r4c8=1=r4c6=7=r4c4=5=r6c4=8=r3c4=1=r1c4=7=r2c5=6=r2c9=9=r2c8
so r2c8 cannot be 9

i didn't bother to read all the above, so i apologize if others covered this more elegantly than me, but here is what i have discovered.

It sometimes comes down to the possibility of two seemingly unsolvable possibilities, and in these possibilities, you have to place one number in one square and the other in the second square, but you cannot tell which one is right by logic until you continue solving the puzzle, easy though the steps are, still for possibly 8 or more numbers, by which time is is nearly impossible to tell whether you've got it right or not - without filling in "cheater" numbers (only cheaters because you are making small notes in the corner of the block. when it's right, it goes through to the end and when it's wrong, you see the conflict and reverse the two numbers.

Having said that, here is what i've discovered: sometimes, either number works! That is a flawed sudoku in my judgment. it's a great weakness of the puzzle when they do that. Rather like a chess puzzle without a "best, shortest, or most elegant" win.

You're describing the last resort method. And the puzzle I posted only has 1 solution, I have solved it.

Just looking for a more elegant solution than guess and fill in until I hit a contradiction.

According to my grid (with lots of little numbers written down)

R1C1 = 157
R1C2 = 57
R1C4 = 17
R2C3 = 79
R2C5 = 67
R2C8 = 19
R2C9 = 169 (have since eliminated 9)
R3C3 = 19
R3C4 = 18
R3C5 = 68
R3C7 = 69
R4C4 = 57
R4C6 = 17
R4C8 = 15
R5C1 = 159
R5C2 = 589
R5C3 = 18
R5C8 = 159 (have since eliminated 1)
R6C1 = 1579
R6C2 = 579
R6C4 = 58
R6C6 = 18
R6C9 = 19
R8C1 = 679
R8C2 = 789
R8C3 = 78
R8C7 = 69
R9C1 = 69
R9C5 = 78
R9C6 = 78
R9C9 = 69

There is a huge grid of strongly linked rows, columns, and boxes, any of which I could use trial & error (aka bifurcation/brute force) to quickly arrive at a solution (including arriving at a contradiction by assuming R2C8 = 9).

I have come up with one promising avenue to solve this one elegantly, although it's still more complex than I like.

It's very similar to trial & error, but more pointed. Essentially I try to prove a certain number is in one of two locations within an element, and therefore eliminate it from anyplace in line with both.

First I assume one of the two is NOT the number in question (preferable one with only one other number). I then follow a chain of conclusions to show that it has to be in the other spot.

For example..

I want to show 9 isn't in R5C1.

If R9C1 = 9,
R5C1 != 9.
If R9C1 != 9, then the following chain of logic follows.
R9C9 = 9
R6C9 != 9
R5C8 = 9
R5C1 != 9.

Either way, R5C1 can't be 9.

Now if only I could eliminate all but one number in a spot with this..

This is a hard one.

Originally posted by geepamoogle
I have come up with one promising avenue to solve this one elegantly, although it's still more complex than I like.

It's very similar to trial & error, but more pointed. Essentially I try to prove a certain number is in one of two locations within an element, and therefore eliminate it from anyplace in line with both.

First I assume one of the two ...[text shortened]... , R5C1 can't be 9.

Now if only I could eliminate all but one number in a spot with this..

Hold on I"ll get Euler on the phone......🙂

i have a sudoku related question too, so if you dont mind, i'll use the same thread.
I recently had a very boring meeting during which i made up a sudoku (9*9). I was wondering now whats the maximum squares i can leave blank in order to get it solved. any suggestions on how to proceed ?

thanks,

polux

hi

Originally posted by polux
i have a sudoku related question too, so if you dont mind, i'll use the same thread.
I recently had a very boring meeting during which i made up a sudoku (9*9). I was wondering now whats the maximum squares i can leave blank in order to get it solved. any suggestions on how to proceed ?

thanks,

polux

I seem to recall hearing that people have shown 17-18 numbered squares are necessary to create a traditional one-answer sudoku.

My experience suggests most of them have 25-28 numbered squares, however.