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   

Programming the 'hidden subset' - Help!
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
Paul

Joined: 11 Aug 2005
Posts: 29
:

Items
PostPosted: Sun Oct 09, 2005 5:56 pm    Post subject: Programming the 'hidden subset' - Help! Reply with quote

Having implemented naked subsets into my solver (www.sudoku.uk.com) i'm stuggling to program a hidden subset algorithm.

Naked subsets were pretty easy to code, because i simply had to loop through each cell in a unit, and check how many times the candidate array existed elsewhere in that unit. If this was the same as the number of candidates, then i had a naked subset.

For a set such as:

{4, 5, 6, 9}, {4, 9}, {5, 6, 9}, {2, 4}, {1, 2, 3, 4, 7}, {1, 2, 3, 7}, {2, 5, 6}, {1, 2, 7}, {8}

Where {1,3,7} form a triplet - what would be the best way to convert a naked subset algorithm to pick this up?
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sun Oct 09, 2005 7:58 pm    Post subject: Reply with quote

You might want to look at this topic. The only thing not explained there is the way to transpose a cell-candidate list into a value-candidate list. However, xyzzy has placed some links to topics that deal with transposing such lists.

It has helped me build the fastest way to search for both hidden and naked subsets.

Lood luck,

Ruud
Back to top
View user's profile Send private message Visit poster's website
Paul

Joined: 11 Aug 2005
Posts: 29
:

Items
PostPosted: Sun Oct 09, 2005 11:57 pm    Post subject: Reply with quote

Thanks. One thing that came out of that post was this:

Quote:
...a naked subset for one set of digits/positions is equivalent to a hidden subset for all the other digits/positions...


Can anyone elaborate on this? Obviously, i do not want to create an entirely new search if naked subsets already expose hidden subsets also.
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Oct 10, 2005 4:16 am    Post subject: Reply with quote

Take your example:

{4, 5, 6, 9}, {4, 9}, {5, 6, 9}, {2, 4}, {1, 2, 3, 4, 7}, {1, 2, 3, 7}, {2, 5, 6}, {1, 2, 7}, {8}

Put it in a matrix:

Code:
 123456789
1...xxx..x
2...x....x
3....xx..x
4.x.x.....
5xxxx..x..
6xxx...x..
7.x..xx...
8xx....x..
9.......x.

The transposed sets are:
{5, 6, 8}, {4, 5, 6, 7, 8}, {5, 6}, {1, 2, 4, 5}, {1, 3, 7}, {1, 3, 7}, {5, 6, 8}, {9}, {1, 2, 3}

These sets represent the valid cell positions for each digit.

Now notice that there is a naked subset {5,6,8} that you can find for the digits 1,3 and 7.
It is like looking at the same data from a different angle.
Back to top
View user's profile Send private message Visit poster's website
Paul

Joined: 11 Aug 2005
Posts: 29
:

Items
PostPosted: Mon Oct 10, 2005 8:23 am    Post subject: Reply with quote

Ok, i see now. This is the value-candidate list you mentioned.

Surely though, in your example:

{5, 6, 8}, {4, 5, 6, 7, 8}, {5, 6}, {1, 2, 4, 5}, {1, 3, 7}, {1, 3, 7}, {5, 6, 8}, {9}, {1, 2, 3} ,

the {5,6,8} triple is a hidden subset, not a naked subset? My algorithm for naked subsets would require the cell-candidate array for 3 to be {5,6,8} , i.e. an exact match of the other candidate arrays in the triple.

Is this maybe where i am going wrong initially?
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Oct 10, 2005 10:08 am    Post subject: Reply with quote

Paul wrote:
My algorithm for naked subsets would require the cell-candidate array for 3 to be {5,6,8} , i.e. an exact match of the other candidate arrays in the triple.

That mistake has been made before, also by me. When looking for a pair, you can look for 2 cells with the same 2 candidates. However, you cannot extend that kind of search to triples and quads. Not all 3 cells need to have all 3 candidates, just as long as together they have only 3 candidates.

{1,2}, {1,3}, {2,3} is also a naked triple, though none of the 3 cells actually has 3 candidates.

On the other issue. When you look at the transposed sets, you will indeed find hidden subsets, but, because of the transposition, with the same technique used for searching naked subsets.
Back to top
View user's profile Send private message Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Mon Oct 10, 2005 8:34 pm    Post subject: Reply with quote

Actually probably easiest is to include a more general subset solver in your code, then apply its logic to naked and hidden subsets as well as X-wings and swordfish.

I've posted an algorithm here which handles subsets via bitwise math. Basically you load up an array with bit flags in two orders (one naked, one hidden; or one by columns and one by rows, if you use this for X-wing/swordfish). Then you call the function and look for a result, which will tell you if a subset was found and which way.
Back to top
View user's profile Send private message
Paul

Joined: 11 Aug 2005
Posts: 29
:

Items
PostPosted: Tue Oct 11, 2005 5:59 pm    Post subject: Reply with quote

Thanks for the input Ruud, and Lummox JR Very Happy . I have now created a subset routine which i can call for naked subsets, or transpose and call for hidden subsets.

It can handle naked subsets like:

{5, 6, 8}, {4, 5, 6, 7, 8}, {5, 6}, {1, 2, 4, 5}, {1, 3, 7}, {1, 3, 7}, {5, 6, 8}, {9}, {1, 2, 3}

or even {1,2}{2,3}{1,3}.

I still feel thought i have not fully grasped the concept of the "limit". I know this is needed when searching through a candidate set, otherwise all sorts of nonsense comes back. For naked subsets, though - what should this be?

Take this example:

{3,4,5,6}, {4,7}, {1,4,5,6}, {8}, {1,4,7,9}, {4,9}, {2}, {1,9}, {3,5,6}

When starting from {1,4,7,9}, you find the remaining 3 sets of the subset - ONLY when searching for sets < size 4. Otherwise virtually all the other sets are included.

For {1,2}{2,3}{1,3} though, you have to pick up sets equal in size to the starting set.

Apologies for the continuous questions - i'd just like to understand fully what i'm doing (even though the program actually works!).
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue Oct 11, 2005 6:39 pm    Post subject: Reply with quote

A discussion on limits between me, xyzzy and lummox JR can be found on this forum.

In short:

Naked subsets and hidden subsets complement each other.
Your example contains a naked subset {1,4,7,9} and a hidden subset {3,5,6}. This accounts for all digits not already bound to a cell (2 and 8).

When there are N unbound digits, N/2 is the limit to search for naked subsets, and (N-1)/2 for hidden subsets.

The lower limit, of course, is 2.

As long as they are within these boundaries, the actual size of the sets themselves is irrelevant. What matters is how many digits there are in the merged sets.

Your example again:
{4,7} ^ {1,4,7,9} = {1,4,7,9} 4 digits, 2 cells (no subset)
{4,7} ^ {1,4,7,9} ^ {4,9} = {1,4,7,9} 4 digits, 3 cells (no subset)
{4,7} ^ {1,4,7,9} ^ {4,9} ^ {1,9} = {1,4,7,9} 4 digits, 4 cells (subset!)

Actually, if you enforce the limits, your code would instead discover the (shorter) hidden subset {3,5,6}
Back to top
View user's profile Send private message Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Tue Oct 11, 2005 6:40 pm    Post subject: Reply with quote

The limit argument in my code exists because I want the solver to be able to ignore higher-order subsets (like triples) on a first pass, so it can rate difficulty on a more human scale. You can safely set that to N/2, where N is the maximum number of candidates (9 in most sudoku), if you want to find any subsets at all. By passing the argument limit=2, I can tell the code to ignore triples and focus on pairs; if it doesn't find any, I'll move on to triples later.
Back to top
View user's profile Send private message
Paul

Joined: 11 Aug 2005
Posts: 29
:

Items
PostPosted: Sun Oct 16, 2005 3:24 pm    Post subject: Reply with quote

Just like to say thanks for all the input guys. have succesfully managed to implement hidden and naked subsets now into my solver. I think (hope Laughing ) it is working 100% now.

Feel free to give it a bash: http://www.sudoku.uk.com

thanks again,
Paul
Back to top
View user's profile Send private message Visit poster's website
MotsCroises

Joined: 08 Dec 2005
Posts: 10
:

Items
PostPosted: Thu Dec 08, 2005 3:43 pm    Post subject: Reply with quote

Hello, (sorry for my bad English)
I just try to add "hidden subset" in my Flash solver. But I can't find a Sudoku that can't be resolved with others and easiest methods…
Do you know where I can find one ? (Or if you can put it in your answer)

Thank you in advance!

Henri
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Dec 08, 2005 4:21 pm    Post subject: Reply with quote

Here is one that can be solved with:
- Hidden Singles
- Naked Singles
- Line-Box interactions a.k.a. Locked Candidates (18x)
- Naked Pairs (1x)
- Hidden Pairs (2x)

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


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

Joined: 08 Dec 2005
Posts: 10
:

Items
PostPosted: Thu Dec 08, 2005 4:34 pm    Post subject: Reply with quote

Ruud wrote:
Here is one that can be solved with:
- Hidden Singles
- Naked Singles
- Line-Box interactions a.k.a. Locked Candidates (18x)
- Naked Pairs (1x)
- Hidden Pairs (2x)

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


Ruud.


Thank you,
But I can resolve this one with "Block and Column / Row Interactions", "Naked Singles/ Pairs" and "Hidden Singles"... without "Hidden Pairs"

Henri
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Dec 08, 2005 5:12 pm    Post subject: Reply with quote

errm.. yes. My solver just detected the hidden pair before the naked pair.

If you want to test individual solving techniques, it may be useful to be able to switch off each solving technique.

Here is one that does require a hidden triple. Be aware that this hidden triple is complemented with a naked quad. So don't tell me it can be solved with naked subsets alone, or find another hobby.

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


Ruud.
_________________
Meet me at sudocue.net
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 -> Programming sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
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