Just One Step

Advanced methods and approaches for solving Sudoku puzzles

Valid

Postby Jumper » Wed Mar 22, 2006 11:08 pm

I almost solved it last night through simple chaining but found what I thought was a double solution in the 1,3 permutation at r1, C2 and C3. Lager was involved so I set it aside. I will finish with your reassurance.

This did however make me ponder if the sort of practice one might get on trying to solve an invalid puzzle might be of huge value when solving the valid ones. If that makes sense. I am unsure.

The 8,3 combination is a Garden of Forking Paths
http://www.geocities.com/papanagnou/
J
Jumper
 
Posts: 8
Joined: 23 September 2005

Re: Valid

Postby tarek » Thu Mar 23, 2006 12:57 am

Jumper wrote:This did however make me ponder if the sort of practice one might get on trying to solve an invalid puzzle might be of huge value when solving the valid ones. If that makes sense.

Many members check the puzzles Validity using programs prior attempting to solve, there has been several occasions where a puzzle has been declared to have a unique solution when there were many.....The Sudoku of shame thread has the examples.

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

Postby re'born » Thu Mar 23, 2006 3:59 am

Okay, I've been working on this long enough. Here is my best attempt.

My reasoning (which utilizes the AUR in ([46], [19])<58>) will show that (4,7)4 > (7,5) is an empty cell. Therefore, (4,7)1 and this will solve the puzzle (given Carcul's restrictions).

(4,7)4 (> (4,1)!4 ) > (4,2)1 (> (1,2)8 > (1, [78])!8 > (3,7)8 > (7,7)2 > (7,5)!2) > (9,2)9 > (9,8)!9 > (5,8)9 > ([46],9)!9 > (6,1)4 (> ([46], 5)<89> > (7,5)!<89>) > (5,3)8 > (7,3)4 > (7,5)!4
re'born
 
Posts: 551
Joined: 31 May 2007

Postby ravel » Thu Mar 23, 2006 9:39 am

Great - i never tried (4,7)4, cause my stupid program could not use the AUR:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Neunmalneun » Thu Mar 23, 2006 10:00 am

Maybe I am wrong, but I think Jumper's first deduction solves the puzzle. If 85 and 15 are no possible combinations for the cells R1C23 then R1C3=3. Simple Sudoku only has singles after that step.
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby Carcul » Thu Mar 23, 2006 10:35 am

rep'nA wrote:Therefore, (4,7)1 and this will solve the puzzle (given Carcul's restrictions).


Hi rep'nA. I hate to disappoint you, but r4c7=1 doesn't solve the puzzle with my restrictions (you still need colors at least once after that). Even then, good work.

Neunmalneun wrote:then R1C3=3. Simple Sudoku only has singles after that step.


Yes, you are wrong. And Simple Sudoku doesn't have only singles after r1c3=3, with colors being needed.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Re: Just One Step

Postby ravel » Thu Mar 23, 2006 1:18 pm

Carcul wrote:... and eventually X-Wings and type-1 URs ...

A type-1 UR is enough with r4c7=1:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Carcul » Thu Mar 23, 2006 3:24 pm

Ravel wrote:A type-1 UR is enough with r4c7=1


Ah yes, you are absolutely right. Good job Rep'nA, Ravel, and others, thanks. The thing is I would prefer a solution without the need for a type-1 UR (that's why I have written "eventually"), but this is ok.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby re'born » Thu Mar 23, 2006 4:52 pm

Carcul,

When you say 'eventually', do you mean in future puzzles? Also, I am reasonably certain (and I can't wait to see a counterexample to this outlandish statement) that any deduction that removes only one candidate, will not be enough to solve the puzzle without UR's and X-wings (you're not allowing BUG's either Carcul?).
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Carcul » Thu Mar 23, 2006 7:05 pm

Hi Rep'nA.

When I say "eventually", I mean "if there is no other possibility (other solution that doesn't need it)".

Rep'nA wrote:Also, I am reasonably certain (and I can't wait to see a counterexample to this outlandish statement) that any deduction that removes only one candidate, will not be enough to solve the puzzle without UR's and X-wings
.

Regarding the present puzzle this might be not true, but I have already solved some puzzles in a single step that removes only one candidate and that solve the puzzle without the need for URs and X-Wings. Regarding the present puzzle, I only could solve it in one step (which doesn't need UR's or X-Wings) by including one candidate, that is, by showing that a candidate must be in a given cell.

Rep'nA wrote:you're not allowing BUG's either Carcul?


That depends on the complexity of the BUG.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Carcul » Sat Mar 25, 2006 5:15 pm

Here is another puzzle that is holding my interest:

Code: Select all
 *-----------------------*
 | 7 . 4 | 9 8 . | . . 3 |
 | . . . | 7 . . | . . 4 |
 | . 1 8 | . . . | . . 9 |
 |-------+-------+-------|
 | . . 2 | . 5 . | 9 . . |
 | . . . | 6 . 3 | 5 . . |
 | 8 . . | . 9 . | 1 . . |
 |-------+-------+-------|
 | . 7 . | . . . | . 2 . |
 | . . . | 5 3 . | . . . |
 | 9 . . | 2 . 8 | . . . |
 *-----------------------*

(Henk Collection, Puzzle #227, rating: 33839)

After the basic logic have been applied we get:

Code: Select all
 *--------------------------------------------------------------------*
 | 7      256    4      | 9      8      1256   | 26     156    3      |
 | 356    23569  3569   | 7      126    1256   | 268    1568   4      |
 | 56     1      8      | 3      246    2456   | 267    567    9      |
 |----------------------+----------------------+----------------------|
 | 1346   346    2      | 8      5      17     | 9      3467   67     |
 | 14     49     79     | 6      127    3      | 5      478    278    |
 | 8      356    3567   | 4      9      27     | 1      367    267    |
 |----------------------+----------------------+----------------------|
 | 3456   7      356    | 1      46     9      | 3468   2      568    |
 | 2      8      16     | 5      3      467    | 467    9      167    |
 | 9      3456   1356   | 2      467    8      | 3467   67     1567   |
 *--------------------------------------------------------------------*

Again, I am interested to know how the various solvers out there would solve this grid from here in a single step. For reference, here is my definition of "single step" (slightly changed regarding the first one I gave):

Single Step: a logical deduction with which the puzzle is solved, i. e., a logical deduction from which all other further logical deductions needed to complete the puzzle are the most basic ones: naked and hidden singles, locked candidates, pairs, triples and quads, and eventually X-Wings, but nothing beyond that (Swordfish, XY-Wing, Colors, type-1 URs, etc).

For this grid, the best I could do until now is a two step solution, with the second step being a XY-Wing.

Every contribution is welcome.

Thanks in advance.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby absolute beginner » Sat Mar 25, 2006 8:51 pm

After some ALS-XZs I got
Code: Select all
+-------------+------------+-----------+
| 9   18  35  | 468 148 36 | 258 28 7  |
| 18  6   7   | 18  5   2  | 9   4  3  |
| 2   4   35  | 89  7   39 | 58  1  6  |
+-------------+------------+-----------+
| 458 189 6   | 2   49  7  | 14  3  58 |
| 3   7   18  | 5   6   48 | 14  9  2  |
| 458 2   489 | 3   489 1  | 7   6  58 |
+-------------+------------+-----------+
| 7   3   48  | 69  248 69 | 28  5  1  |
| 148 5   2   | 148 3   48 | 6   7  9  |
| 6   189 189 | 7   128 5  | 3   28 4  |
+-------------+------------+-----------+


this nonrepetive path in the bilocation graph solves the puzzle:
r9c5=(2)=r9c8=(8)=r1c8=(2)=r1c7=(5)=r3c7=(8)=r3c4=(9)=r3c6=(3)=r1c6=(6)=r1c4=(4)=r1c5=(1)=r9c5
remove 8 from r9c5
remove 8 from r1c7
remove 8 from r1c4
remove 8 from r1c5
absolute beginner
 
Posts: 22
Joined: 26 February 2006

Postby absolute beginner » Sat Mar 25, 2006 8:52 pm

sh... wrong threat, sorry
absolute beginner
 
Posts: 22
Joined: 26 February 2006

Postby Jeff » Sat Mar 25, 2006 9:09 pm

absolute beginner wrote:.......this nonrepetive path in the bilocation graph solves the puzzle:
r9c5=(2)=r9c8=(8)=r1c8=(2)=r1c7=(5)=r3c7=(8)=r3c4=(9)=r3c6=(3)=r1c6=(6)=r1c4=(4)=r1c5=(1)=r9c5

Hi Absolute beginner, This is the longest strong inference chain I have ever seen. Well spotted.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby absolute beginner » Sat Mar 25, 2006 11:58 pm

Thank you, Jeff,

I found it with pencil and paper ( I think, I should
change my nick:D ), because my implementation
of Eppstein's gadgets driving me to madness!
But the next step will be an implementation
of Carcul's proposition to find a solution with
only one non-trivial step.

Ok, and its not a "path", its a circle
and I meant "thread" not "threat"
and its the right thread
mea culpa,mea culpa...
absolute beginner
 
Posts: 22
Joined: 26 February 2006

PreviousNext

Return to Advanced solving techniques

cron