Sudokus with an original rare shape

Everything about Sudoku that doesn't fit in one of the other sections

Postby r.e.s. » Sat Jul 01, 2006 2:14 pm

ravel wrote: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".)

ravel wrote: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.)

ravel wrote: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.
Last edited by r.e.s. on Sat Jul 01, 2006 11:31 am, edited 2 times in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby m_b_metcalf » Sat Jul 01, 2006 2:59 pm

gsf wrote:
Ocean wrote: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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8339
Joined: 15 May 2006
Location: Berlin

Postby daj95376 » Sat Jul 01, 2006 6:28 pm

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!!!]
Last edited by daj95376 on Sat Jul 01, 2006 5:50 pm, edited 2 times in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby JPF » Sat Jul 01, 2006 8:19 pm

daj95376 wrote:
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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby m_b_metcalf » Sat Jul 01, 2006 9:22 pm

daj95376 wrote: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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8339
Joined: 15 May 2006
Location: Berlin

hit me harder

Postby claudiarabia » Sat Jul 01, 2006 9:41 pm

Carcul wrote: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
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby Carcul » Sat Jul 01, 2006 10:17 pm

Carcul wrote: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.

Claudiarabia wrote: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
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ravel » Sun Jul 02, 2006 12:16 pm

r.e.s. wrote: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.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Ocean » Sun Jul 02, 2006 4:11 pm

r.e.s. wrote:
Ocean wrote:
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.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby r.e.s. » Sun Jul 02, 2006 7:07 pm

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.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby claudiarabia » Sun Jul 02, 2006 7:18 pm

Carcul"][quote="Carcul wrote: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
Last edited by claudiarabia on Tue Jul 04, 2006 5:30 am, edited 2 times in total.
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby Ocean » Sun Jul 02, 2006 7:47 pm

r.e.s. wrote: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.]
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby claudiarabia » Sun Jul 02, 2006 11:21 pm

tso wrote: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
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby udosuk » Tue Jul 04, 2006 9:05 am

claudiarabia wrote:
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 !?:!::?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ravel » Tue Jul 04, 2006 9:49 am

This puzzle is certainly too hard to be solvable with a short forcing chain.
ravel
 
Posts: 998
Joined: 21 February 2006

PreviousNext

Return to General