View previous topic :: View next topic |
Author |
Message |
| gonzo
| Joined: 18 Jan 2006 | Posts: 4 | : | | Items |
|
Posted: Wed Jan 18, 2006 7:40 am Post subject: Triples (123) (12) (23) |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Wed Jan 18, 2006 7:56 am Post subject: |
|
|
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 |
|
|
| gonzo
| Joined: 18 Jan 2006 | Posts: 4 | : | | Items |
|
Posted: Wed Jan 18, 2006 3:51 pm Post subject: |
|
|
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 |
|
|
| eclark
| Joined: 28 Dec 2005 | Posts: 70 | : | | Items |
|
Posted: Wed Jan 18, 2006 4:33 pm Post subject: |
|
|
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
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 |
|
|
| gonzo
| Joined: 18 Jan 2006 | Posts: 4 | : | | Items |
|
Posted: Wed Jan 18, 2006 5:35 pm Post subject: |
|
|
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 |
|
|
|