Downscoring some "Sudokus We Can't Solve By Logic"

Advanced methods and approaches for solving Sudoku puzzles

Downscoring some "Sudokus We Can't Solve By Logic"

Postby algol » Sun Feb 12, 2006 7:08 pm

Code: Select all
Puzzle #1
Guesses:  2
Difficulty score:  2385

This puzzle actually needs only one guess!

In addition to the candidates grid I'm using nine additional grids, one for each number.
They help me to check continuously and easily for the two rules -
-  «Single row in one box» (1R1B)
-  «Pair rows in two boxes» (2R2B)

e.g.
1R1B in box 1:

1 1 1  1 1 1  1 1 1
- - -  1 1 1  1 1 1
- - -  1 1 1  1 1 1

->

1 1 1  - - -  - - -
- - -  1 1 1  1 1 1
- - -  1 1 1  1 1 1

and
2R2B in boxes 1 and 2:

1 1 1  1 1 1  1 1 1
1 1 1  1 1 1  1 1 1
- - -  - - -  1 1 1

->

1 1 1  1 1 1  - - -
1 1 1  1 1 1  - - -
- - -  - - -  1 1 1

Solving the given puzzle:

1.  Single 6 in box 1
2.  Hidden pair 1, 8 in box 5
3.  Quartett 1, 5, 6, 9 in column 9
    -> R5C9 = 7
4.  Pair 2, 9 in row 5
    -> R5C6 = 6
5.  Trio 2, 7, 9 in column 5
6.  Quartett 1, 2, 3, 6 in row 8
    -> R8C2 = 4
    -> R4C1 = 4
    -> R9C1 = 7
    -> R8C4 = 7
    -> R8C3 = 8
7.  Pair 5, 9 in row 2
    -> R5C4 = 2
    -> R6C3 = 2
    -> R7C1 = 2
    -> R6C1 = 9
    -> R2C5 = 2
    -> R9C6 = 2
    -> R9C4 = 8
    -> R6C6 = 8
    -> R4C7 = 8
    -> R4C4 = 1
    -> R6C2 = 1
    -> R9C3 = 1
    -> R5C3 = 3
    -> R4C2 = 5
    -> R5C7 = 5
    -> R2C3 = 5
    -> R2C2 = 9
    -> R7C3 = 9
    -> R2C1 = 8
    -> R4C8 = 6
    -> R4C5 = 9
    -> R4C3 = 7
    -> R6C5 = 7
    -> R1C9 = 8
    -> R6C9 = 4
    -> R2C8 = 7
    -> R1C6 = 7

Now, the «logic» stops.
Each of the numbers 4 and 5 has only two patterns left.
So, start bifurcating with the pair 4, 5 in R7C6:

a.  R7C6 = 5? soon leads to a contradiction, e.g. C9 = 6, 6.
b.  R7C6 = 4! smoothly produces the (unique) solution of the puzzle!

So, for this puzzle #1 only one guess is required!


Puzzle #3 requires only one guess, too!

Puzzle #4 doesn't require any guess at all!
It is completely solved by logic!
algol
 
Posts: 3
Joined: 08 February 2006

Postby vidarino » Sun Feb 12, 2006 10:02 pm

No puzzles *require* guessing. If it's a valid puzzle with only one solution, it can be solved with logic alone. Finding the logical deductions is the challenge. To me, guessing is equivalent to giving up. (I will readily admit that on a couple of occasions I have given up on some puzzles, but not without a certain amount of regret.)

That aside, which puzzles are you talking about??
vidarino
 
Posts: 295
Joined: 02 January 2006

Downscoring some "Sudokus We Can't Solve By Logic"

Postby algol » Mon Feb 13, 2006 9:01 pm

In www.sudokusolver.co.uk/grids_nologic.html
Pete Wake gives 30 puzzles which have a unique solution, but require bifurcation, that means, at some point you have to trace for both candidates of a pair in a certain cell (or for the same number in two different cells) whether it leads to the solution or to a deadlock (two cells in a row/column/box with the same unique candidate or one cell without any more candidates).
This bifurcation he calls "guess", and for every puzzle he indicates the "number of guesses required".
My previous post only showed that for some of his puzzles the "number of guesses/bifurcations" is lower than he estimates.

vidarino, I agree with you that the word "guess" is inappropriate here because it suggests that you every now and then go and choose for any cell any of the digits 1 to 9 and proceed with your choice the classic (logical) way until you come to a solution, or else revoke your choice.
That's brute force and definitely not the state of the art of solving a sudoku, not even by a computer program!
algol
 
Posts: 3
Joined: 08 February 2006

Postby vidarino » Mon Feb 13, 2006 9:47 pm

I ran the list through my solver, and only *one* of them required guessing. The rest were solvable with a variety of other semi-advanced techniqes, such as Almost Locked Sets, Nice Loops (including several Turbot Fishes), and some were solved with nothing but an XYZ-Wing. So that list doesn't appear to be up to par on the latest tricks.:)

The one that needed a guess could be persuaded to be solved with a Forcing Chain after I increased the default search depth (at the cost of processing time), but FC might be regarded as trial and error by some, since it's basically a local exhaustive search. (The longest chain needed was 12 steps long, by the way.)
vidarino
 
Posts: 295
Joined: 02 January 2006

Re: Downscoring some "Sudokus We Can't Solve By Logic&q

Postby aeb » Mon Feb 13, 2006 9:49 pm

algol wrote:In www.sudokusolver.co.uk/grids_nologic.html
Pete Wake gives 30 puzzles which have a unique solution, but require bifurcation

Hmm. I find these puzzles very easy. For example, the first is solved by
(1,1)3 > (1,5)5 > (3,6)1 > (3,1)3 > (1,1)1
so that (1,1) is 1. Maybe this is called XY-wing or so.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby re'born » Tue Feb 14, 2006 1:37 am

And #4 which supposedly requires 13 guesses and rates the most "difficult" can be cracked with (at most) multiple coloring, an xyz-wing and a BUG at the end.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby tso » Tue Feb 14, 2006 6:07 am

That site is very behind the curve as far as solving tactics and hasn't been updated in some time.
tso
 
Posts: 798
Joined: 22 June 2005

Postby tarek » Tue Feb 14, 2006 6:43 am

here are the puzzles as they appear on the site:
Code: Select all
 . 2 . | . . . | . . . 
 . . . | 6 . . | . . 3 
 . 7 4 | . 8 . | . . . 
-------+-------+------
 . . . | . . 3 | . . 2 
 . 8 . | . 4 . | . 1 . 
 6 . . | 5 . . | . . . 
-------+-------+------
 . . . | . 1 . | 7 8 . 
 5 . . | . . 9 | . . . 
 . . . | . . . | . 4 . 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



None were really that tough.....

Tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: Downscoring some "Sudokus We Can't Solve By Logic&q

Postby algol » Tue Feb 14, 2006 4:39 pm

Thanks to you all for your comments!
Your investigations clearly show that the Post Subject rather should have been "Downscoring all..." instead of "... some ...":)

BTW, I don't know how the "difficulty score" is calculated except for the "number of guesses" which adds up 1000 scores each.
algol
 
Posts: 3
Joined: 08 February 2006


Return to Advanced solving techniques