Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Question about constrained subsets

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
maarten

Joined: 16 Jun 2006
Posts: 7
:
Location: The Netherlands

Items
PostPosted: Wed Aug 23, 2006 9:33 am    Post subject: Question about constrained subsets Reply with quote

Hello all,
Very interesting to read all the stuff in here. I read about constrained subsets a while ago, and am now trying to build my solver with this technique.
Doing that I bumped in some difficult to understand stuff. I am now working on Finned X-Wing (after X-Wing, that too was a tough nut).

For this sudoku

Code:

..4.5.9......7...637......2..95...8...12.43...6...92..2......931...4......6.2.7..


i am getting the following solvingstep after the simpler techniques

Code:

6    18   4   |3    5    2   |9    7    18
59   189  2   |4    7    18  |58   3    6
3    7    58  |6    9    18  |458  145  2
--------------------------------------------
4    2    9   |5    3    6   |1    8    7
7    5    1   |2    8    4   |3    6    9
8    6    3   |7    1    9   |2    45   45
--------------------------------------------
2    48   578 |1    6    57  |458  9    3
1    389  578 |89   4    357 |6    2    58
59   3489 6   |89   2    35  |7    145  1458

Found a Finned X-Wing-2 with candidate 8 in groups R1/B77 and C2/C9 with Fin R7
- removing from cell(s) R7C2


Rx stands for row x, Cx for column y, and Bxy stand for the block in row x and column y, and RxCy refers to cell x,y.

I am having difficulty seeing the logic in this step. It appears to be correct, because while it doesn't solve the sudoku (more advanced methods are needed), it does not take incorrect steps if I compare it to my non-constrained-subset-solver. It takes another step like this

Code:

6    18   4   |3    5    2   |9    7    18
59   189  2   |4    7    18  |58   3    6
3    7    58  |6    9    18  |4    15   2
--------------------------------------------
4    2    9   |5    3    6   |1    8    7
7    5    1   |2    8    4   |3    6    9
8    6    3   |7    1    9   |2    45   45
--------------------------------------------
2    4    578 |1    6    57  |58   9    3
1    389  578 |89   4    357 |6    2    58
59   389  6   |89   2    35  |7    14   14

Found a Finned X-Wing-2 with candidate 5 in groups C1/C7 and R2/B71 with Fin R7
- removing from cell(s) R7C3


I can understand the x-wing and finned x-wing with just rows and columns, but this type with blocks in it, i am having difficulty validating my solver.

The question: are these steps correct?

Greetz
Maarten
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Aug 23, 2006 12:00 pm    Post subject: Reply with quote

At this stage:

Code:
.---------------.---------------.---------------.
| 6    18   4   | 3    5    2   | 9    7    18  |
| 59   189  2   | 4    7    18  | 58   3    6   |
| 3    7    58  | 6    9    18  | 458  145  2   |
:---------------+---------------+---------------:
| 4    2    9   | 5    3    6   | 1    8    7   |
| 7    5    1   | 2    8    4   | 3    6    9   |
| 8    6    3   | 7    1    9   | 2    45   45  |
:---------------+---------------+---------------:
| 2    48   578 | 1    6    57  | 458  9    3   |
| 1    389  578 | 89   4    357 | 6    2    58  |
| 59   3489 6   | 89   2    35  | 7    145  1458|
'---------------'---------------'---------------'


There is a Swordfish digit 8 in R189-C149 with a fin in R8C3
The complement is in C367-R237 with the same fin in R8C3

Both swordfishes eliminate R7C2.

Result from your program is correct, but not the way it is reported.

Ruud
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
Jean-Christophe

Joined: 19 Mar 2006
Posts: 126
:
Location: Belgium

Items
PostPosted: Wed Aug 23, 2006 3:24 pm    Post subject: Reply with quote

It could also be solved with grouped (AKA finned) Turbot fish :

Grouped Turbot Fish on 8 with 3 links R1C2 == R1 == R1C9 .. N3 .. R23C7 == C7 == R7C7 -> R7C2 <> 8

The group/fin is in R23C7
N3 means nonet/block/box/... # 3 in R123C789
The == are for strong links, the .. are for weak links.

Then a (regular) Turbot fish :

Turbot Fish on 5 with 3 links R7C7 == C7 == R2C7 .. N3 .. R3C8 == R3 == R3C3 -> R7C3 <> 5
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron