The New Sudoku Players' Forum

[r.e.s.]

susser 2.5 needs "Simple Forcing Loops" and/or "Comprehensive Forcing Chains" for the 3 puzzles, which (in general) cannot be expressed as xy-chains.

Susser 2.5.4 used "Simple Forcing Chains" (xy-chains) to solve these, not the other types of chain. The strategies Susser reported it used are listed in my posting! (I suspect you've not de-selected the other "advanced methods" in Susser's list of allowed "Heuristics".)

xy-chains are bivalue/bilocation chains that always start in a bivalue cell with candidates xy, showing that a y in the cell would lead to an x in another one, so that either of the 2 cells must hold an x. Then x can be eliminated from cells that see both.

It's an inessential matter of terminology whether the cell in which an elimination occurs is regarded as part of the xy-chain. If we do so -- as Susser's "Simple Forcing Chains" do -- then each chain eliminates just one candidate, and there may be more than two candidates in that cell. (But this is not relevant to the point of my posting.)

Only Simple Forcing Chains (bivalue chains with contradiction) always can be expressed as xy-chains.

And that is what Susser used to solve these.

EDIT(1): Added comment on selecting Susser's allowed solving-methods.
EDIT(2): Added comment on Susser's terminology for xy-chains.

[m_b_metcalf]

Not sure how to attack this. A few attempts resulted in puzzles with two solutions (as known from previous postings). My programs are not suitable for a complete search in this pattern. Was also not able to do a thorough analysis. So as far as I know there might still be valid puzzles hiding somewhere. Might come back to it later if I come up with better strategies.

I also let a program go for a day or so and got down to 2 solutions
with an algorithm slower than ocean's

I let each of my two programs run for an hour real time, equivalent to a million tries each, but with no success. Seems to be a pathological pattern.

Regards,

Mike Metcalf

[daj95376]

I took a known solution and masked it off using udosuk's pattern. Then I ran it through gsf's backtracking solver from the Programmers Forum. Here are the intermediates and the final output.

Code: Select all

<
567183429183492756942567138835746291624931587719258643256819374378624915491375862 solution
xxxxxxxxxxxx...xxxxxx...xxxx.......xx...x...xx.......xxxx...xxxxxx...xxxxxxxxxxxx mask
567183429183...756942...1388.......16...3...77.......3256...374378...915491375862 puzzle
>
567183429183429756942657138835796241614832597729541683256918374378264915491375862
 multiple solutions


Now, whether or not working backwards proves anything, I don't know.

[Edit: I should have given it some more thought and realized that I couldn't demonstrate anything this way. Not every solution will work with every pattern!!!]

[JPF]

Code: Select all

<
567183429183...756942...1388.......16...3...77.......3256...374378...915491375862
 multiple solutions


Correct, 392 solutions.

For two examples of puzzles with 2 solutions, see here.

I tried this more difficult pattern :

Code: Select all

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



80 solutions...
[edit]

JPF

[m_b_metcalf]

I took a known solution and masked it off using udosuk's pattern. Then I ran it through gsf's backtracking solver from the Programmers Forum.
[snip]
Now, whether or not working backwards proves anything, I don't know.

That's the algorithm each of my two programs use. And each did that with a million different grids -- unsuccessfully.

Regards,

Mike Metcalf

[claudiarabia]

This pattern is also very pleasant: is it possible to make your puzzle harder, Claudiarabia? Thanks, Carcul

yes, I try to make them harder. This is the hardest I did, I suppose. I still feel to be at the beginning. That's why I concentrate on the shape. When I create a puzzle it mostly turns out to be one of the mild sort. Sometimes I try to refine it but it's o.k. to have difficult and easy ones in this thread. There must be some strategies to make it hard right from the beginning but I will become better.

Congrats to your victory over England today

Cheers Claudia

[Carcul]

is it possible to make your puzzle harder, Claudiarabia?

What I wanted to say was if it is possible to make an harder puzzle with that pattern, but I think you have also answered this. Perhaps there are some patterns for whom its very difficult to make hard grids.

Congrats to your victory over England today

Thanks! It was another terrible game for the heart, and after 90 minutes of suffering I had to run away from the front of the TV and do something else. It's a pity when a match needs to be decided with the "wheel of fortune" of penalties, but, that is part of futebol. However, I have to congratulate England because they have also played very well and with fair-play.
Well, France is next. Perhaps Germany and Portugal may meet in the final match, who knows.

Regards, Carcul

[ravel]

Susser 2.5.4 used "Simple Forcing Chains" (xy-chains) to solve these, not the other types of chain.

Ah, i have 2.5.0. When i de-selected forcing loops and comprehensive forcing chains, it needed tabling to solve the puzzles. I now tried it with the older version 2.0.4. This one found the simple forcing chains.

[Ocean]

Code: Select all

Slash pattern: not solved with xy-chains alone [...]

Not sure what's meant by "xy-chains alone", but a few puzzles in this part of your list are solved by Sudoku Susser with only xy-chains ("Simple Forcing Chains") and simple moves including naked pairs & line-box interactions ...

000000012000000345000006780000067400000538000001940000045300000892000000760000000
15 x Simple Forcing Chains [...]

000000012000000345000006780000063800000549000003210000052400000974000000860000000
2 x Simple Forcing Chains [...]

For this one a naked quad is used ...
000000012000000345000006780000067100000238000002940000049300000613000000780000000
2 x Simple Forcing Chains [...]

Thanks for analyzing the puzzles and pointing at these examples!

The puzzles listed as "not solved with xy-chains alone" actually meant "not solved by my solver": This solver had implemented most (but not all) basic techniques, plus xy-chains (but not xy-rings).

There were two reasons these puzzles were not solved:

1. The logic for preventing chains to continue in endless loops had the unwanted side-effect that most xy-rings were not discovered. This flaw is now corrected (hopefully). After the fix my solver now solves the first puzzle with 6 xy-chain/ring/wing "steps" (total 22 candidate eliminations). One "step" consists of eliminations by all the smallest chains/rings/wings available (1 or more). The second puzzle is solved with two such steps (xy-ring followed by xy-wing).

2. For the third puzzle: The 'naked quad' is still not implemented in the solver, so naked quads will not be found unless they have hidden triples or doubles as counterparts. Checking manually: After the naked quad is applied, the puzzle can be solved with elimination by an xy-chain of cycle length 6, followed by an xy-wing.

[r.e.s.]

Ocean,

I think there might be a misunderstanding about some sort of "xy-ring" being needed to solve the first two puzzles I mentioned. The only strategies needed are listed in my first posting; in particular, an elimination by a "Simple Forcing Chain" is exactly the same as an elimination by an xy-chain. No "xy-rings" or "Simple Forcing Loops" are needed -- plain old xy-chains are sufficient.

[claudiarabia]

is it possible to make your puzzle harder, Claudiarabia?What I wanted to say was if it is possible to make an harder puzzle with that pattern... Perhaps there are some patterns for whom its very difficult to make hard grids.

Actually I don't know if this pattern is useful for doing hard grids. I'm just trying this and that. I always thought the x-shape would be difficult to produce any pattern at all and I learned it better in this forum.

Here I produced another one which may be a bit harder. You will take resort to the dancing links I suppose.

Code: Select all

5 . . 1 . . . . 4
. . 8 . 2 . . . .
. 2 . . . 3 . . .
4 . . . . . 3 . .
. 5 . . 9 . . 7 .
. . 2 . . . . . 1
. . . 3 . . . 5 .
. . . . 8 . 2 . .
1 . . . . 4 . . 9           G-Froylain

Claudia

[Ocean]

Ocean,

I think there might be a misunderstanding about some sort of "xy-ring" being needed to solve the first two puzzles I mentioned. The only strategies needed are listed in my first posting; in particular, an elimination by a "Simple Forcing Chain" is exactly the same as an elimination by an xy-chain. No "xy-rings" or "Simple Forcing Loops" are needed -- plain old xy-chains are sufficient.

True. No loop structure is needed, only the chains. Sorry if I used wrong terminology, or misunderstood what kind of logic named techniques represent.

[My comment was an effort to explain why the solver missed the solution in these cases: This happened generally when at least one necessary chain had ring structure. Hopefully fixed now.]

[claudiarabia]

SOLO, a free applet in Simon Tatham's Portable Puzzle Collection,

Hi, Tso! I like this one most of your square-collection. It has the Gordon-mentioned Band-rotation mentioned in his canon of Formalized symmetry, really a rare pattern to find.

Code: Select all

 1 2 6 . . . . . .
 3 . 4 . . . 2 1 6
 9 8 5 . . . 4 . 3
 . . . . . . 7 2 8
 . 6 7 5 . . . . .
 . 4 . 9 . . . . .
 . 1 9 2 . 6 3 4 .
 . . . . . 9 . 8 .
 . . . . . 3 6 9


The Tatham-collection is nice. I never dreamt of making Sudokus with 3x6-boxes!

Claudia

[udosuk]

Code: Select all

5 . . 1 . . . . 4
. . 8 . 2 . . . .
. 2 . . . 3 . . .
4 . . . . . 3 . .
. 5 . . 9 . . 7 .
. . 2 . . . . . 1
. . . 3 . . . 5 .
. . . . 8 . 2 . .
1 . . . . 4 . . 9           G-Froylain

Could someone demonstrate a good short forcing chain for this one please !?

[ravel]

This puzzle is certainly too hard to be solvable with a short forcing chain.