The New Sudoku Players' Forum

[PTP]

Hi.

I'm trying to write a java program to solve Su Doku in a strange way - rather than defining rows, columns, and boxes, I've generalized all of these into constraints, which allows the program to scale to allow puzzles with extra or irregular regions, as well as multiple Su Doku such as the Samurai.

My problem is in generalizing the advanced techniques. Generalizing the basic ones was much easier using my system, but I'm at a loss to come up with a way to find X-wings, swordfish, and other patterns.

For example, generalizing this rule was easy:

Code: Select all

1 2 X|. . .|. . .
. . X|X X X|X X X
7 8 X|. . .|. . .
-----+-----+-----
. . .|. . .|. . .
. . 3|. . .|. . .
. . .|. . .|. . .
-----+-----+-----
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .


3 cannot be anywhere marked with an X because the only possibilities in the upper-left box are in row 2, which will eliminate the rest of that row. This is generalized by saying: If all of the possibilities for a given value within constraint #1 also lie entirely within constraint #2, then that value is eliminated from the rest of constraint #2.

Can anyone help me out by generalizing any of the advanced techniques?

[ravel]

Let me try for x-wing:
If there are exactly 2 possibilities for a number both in constraint 1 and 2 and there are constraints 3 and 4, that each contain 2 of them (one from constraint 1 and one from constraint 2), the number can be eliminated from the rest of constraints 3 and 4.
Can you use that?

[udosuk]

A more detailed definition of x-wing:

Suppose N is the digit we're analysing...

2 cells A & B are strongly-linked within constraint 1 (one of them must contain the N on that constraint)

2 cells C & D are strongly-linked within constraint 2

A & C are weakly-linked within constraint 3 (they both contain N as a candidate but there are others cells along constraint 3 that also have N as a candidate)

B & D are weakly-linked within constraint 4

Then all Ns could be eliminated from all cells on constraints 3 & 4 outside A, B, C, D...



As an extension:

Even if B & D are not weakly-linked, all cells which weakly-linked to both B & D simulaneously ("seeing" both B & D) must have N eliminated (otherwise we're forced to have A & C both containing N, and will have 2 Ns on constraint 3...)

This is called a Turbot-fish/Double Crossover...

[PTP]

Thanks, udosuk, that's exactly what I needed!

Although, since what I already have can already solve most puzzles, it may be better (both in terms of how long it would take to code, and how long the program would run) it might just be better to solve as much as possible with basic techniques and then just use brute force, rather than search a huge combination of possible values, cells, and constraints that would all have to align to form an x-wing.

But then again, that's no fun!

And anyway, my goal was to create a program to solve some of the strange variations such as extra regions or huge multiple Su Doku, which are typically more difficult just because of the huge scale, rather than requiring the player to use these advanced techniques. Most "normal difficulty" Samurai require nothing more than only-candidates, naked singles, and naked pairs.

[algernon]

I have another definition for fishy structures, which is the same for
normal 9x9, but more general on other topologies. In 9x9 a x-wing
between rows and boxes makes no sense, as simpler techniques would
have the same eliminations. But in "general" sudoku rows and boxes
have no clear distinction. (Even in 9x9 jigsaw sudoku some "boxes" might
be very long and x-wing makes sense there).

So the more general aspect kicks in, where we have houses ("constraints")
which overlap in more than one cell, and the candidate in question might
live in more than one of the cells, so there is no strong link.

My definition goes like:

We have a set A of n constraints, which are pairwise distinct (no overlap).
We have another set B of n constraints, which are pairwise distinct, and
where each constraint in B overalps with each constraint of A.
Now if, for a specific colour C, there are no candidates in A - B, all
candidates must lie in the intersection, so no candidate is in B - A.

For normal 9x9 sudoku, the evaluation of this pattern is quite expensive.
There are 27 constraints, and for swordfish, you must select six of
them. (27 * 26 * 25 combinations for set A times 24 * 23 * 22
combinations for set B) You can get lower numbers if you check certain
conditions on the way (like distinct-ness, overlaping...). My java
implementation needs 30ms to check for swordfish on 9x9, w/o
using knowledge about rows/columns.

Michael



Michael