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   

Triples (123) (12) (23)

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

Joined: 18 Jan 2006
Posts: 4
:

Items
PostPosted: Wed Jan 18, 2006 7:40 am    Post subject: Triples (123) (12) (23) Reply with quote

My code is checking the rows, columns and subgrids for the (123) (12) (23) pattern.

I realize that what you're really looking for is a pattern of 123 and then two of the following three - 12, 23 or 13, those being the three other two number possibilities from the triple.

What I'm wondering, however, is there a possibility that you could have your 123 and all three of the two number possibilites from that, not only 12 and 23 but the 13 as well, or is my code okay in that once I find 123 and 12 and 23 (or 13) that I can go ahead and start removing those three numbers from all the other cells.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Jan 18, 2006 7:56 am    Post subject: Reply with quote

Hi and welcome to the forum.

When you are looking for naked triples, you only need to check for 3 cells in a house that together have only 3 candidates.

The pattern that you're looking for satisfies this requirement. If you look around in the programming forum, you can find some topics on how to code subset searching routines. These routines do not look for specific patterns, but perform a bitwise OR of the candidates and then count the bits.

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

Joined: 18 Jan 2006
Posts: 4
:

Items
PostPosted: Wed Jan 18, 2006 3:51 pm    Post subject: Reply with quote

Thanks for the welcome, I was pretty stoked to find a place where I'm not the only one who finds programming a Sudoku solution a more interesting problem than actually solving the puzzles myself.

Quote:
When you are looking for naked triples, you only need to check for 3 cells in a house that together have only 3 candidates.


That makes it clearer in my head what I'm actually looking for with the triples, thanks!

Quote:
The pattern that you're looking for satisfies this requirement. If you look around in the programming forum, you can find some topics on how to code subset searching routines. These routines do not look for specific patterns, but perform a bitwise OR of the candidates and then count the bits.


Hmmm . . . that part you lost me on. The way I have it working, I teach my program each solving technique one by one. I'll be interested to see the other approaches, although I think I may stick with mine because it is a bit more interactive and educational for the user in that I let them choose their solving strategy and they get to see each strategy unfold.
Back to top
View user's profile Send private message
eclark

Joined: 28 Dec 2005
Posts: 70
:

Items
PostPosted: Wed Jan 18, 2006 4:33 pm    Post subject: Reply with quote

I just posted my code to search for these subsets. You might want to look at the code. I rather like it though I may be a little biased Laughing

Any way the only advice I would give is that you have to be careful to no just look for positions with three posibilities and then see if there are two others that have only those posibilities. That will get most of them but will miss some.

{12}{23}{13} <-- This is a valid trple and if you are only looking for positions with three you will miss it.

Also a good idea for a humanistic solver is to look for the smalllest subsets first then look for bigger onse.

Ruud was talking about bitwise or | <- in most languages

That's because a lot of us use a int to hold all of the posibilites for a position. and each bit position of that integer is then representative of a number posibility. This makes accessing all of the posibilites on one square much faster than a large array.

so then to if I have two positions

int square_one;
int square_two;

then to find the union of the two (all of the posibilites that either of them have)

int union = square_one | square_two;

and to find the intersection you just

int intersection = square_one & square_two;

I hope that helped
Back to top
View user's profile Send private message
gonzo

Joined: 18 Jan 2006
Posts: 4
:

Items
PostPosted: Wed Jan 18, 2006 5:35 pm    Post subject: Reply with quote

I went about it a bit of an unconventional way - I have a two-dimentional string array and I use Replace$ to remove the proper digits. It works quite nicely and also will make it easy to add support for alpha-numeric puzzles.

In the same way, I can combine all the strings in a scope and a simple

iOccurrences = replace$(sCombined, sChar, vbNullstring) - len(sCombined)

lets me know how many of sChar is in the scope.

I'll have to check out your code, thanks for the post.
Back to top
View user's profile Send private message
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