Set Logic Solns: Top1465#77, Easter Mons. Golden Nugget

Advanced methods and approaches for solving Sudoku puzzles

Postby Allan Barker » Mon Sep 15, 2008 9:15 pm

Hum, platinum blond sounds more like a monster.

I solved the first of the two puzzles, which might better be named pot-metal pony if metal quality reflects difficulty. The puzzle was relatively easy, maybe less difficult that the Top1465 #3, which would be the closest reference that I have worked with. Below is a simple rating with number of required sets and nodes. (Blue = no. of strong sets, Red = no. of nodes)

Image

If that's the case, I would read Champagne's comments to mean that the 2 puzzles cause problems for the solver, not that they are extremely tough beyond other puzzles. I noticed that the first puzzle has a high degree of interlocked logic, for lack of a better word. I have also seen that such logic can be problematic, although I have no idea what it would do to other solvers.

Below is a very simple example from the puzzle of what I mean by interlocked logic. The logic on the right can eliminate two candidates (red cubes) but not with the same logic. If the columns are weak links (left image) then the logic eliminates 7r4c5 (orange cube). If the rows are weak links (not shown) then 7r1c4 is eliminated. Of course, there is nothing wrong with the logic on the right, but it follows different rules. Note, colored bars are strong links and white bars are weak links.

This puzzle has more than its share of such logic. (Click for larger image)

Image

Allan

Edit: for clarity
Last edited by Allan Barker on Tue Sep 16, 2008 5:50 am, edited 1 time in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby champagne » Tue Sep 16, 2008 12:18 am

Allan Barker wrote:Hum, platinum blond sounds more like a monster.

1) I solved the first of the two puzzles, ....
2) If that's the case, I would read Champagne's comments to mean that the 2 puzzles cause problems for the solver, not that they are extremely tough beyond other puzzles. I noticed that the first puzzle has a high degree of interlocked logic, for lack of a better word. I have also seen that such logic can be problematic, although I have no idea what it would do to other solvers.
Allan


1) Grate. I have now to dig in your process to catch the underlying logic.

I guess the solution will be available soon on your site.


2) These 2 puzzles cause problem to "my" solver with the set of rules he his using. I have not been surprised to see puzzles not solvables with that limited set.

I had no incentive up to now to enter additionnal logic. I was waiting for a sample file of puzzles to see what kind of logic would fill the gap.

It seems that your logic is complementary to what is already in my solver, so I will try to use it.

As tarek noticed, we will have then to rework the entire file to rank hardest puzzles, but that is life.


ps: as far as I remember, PB is no so difficult. Silver plate is for me the monster.

edit: I checked that point wtih the current version of my solver. Not so easy, but significantly below NG and SP. Limit down in my list of hardest.

champagne
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

Postby Allan Barker » Tue Sep 16, 2008 10:06 am

Champagne, it will take a couple of days to get images and diagrams on to my website and will let you know when I do.

One more point of interest. I have 2 different programs for solving Sudoku grids. One is an ordinary backtracking algorithm and the other is a variant of Algorithm X. Both find your puzzle (now Fata Morgana !) more difficult to solve than GN by a factor of 3 or 4. The algorithm X type program is invariant to isomorphic operations, I don't know about the other. Below are results in arbitrary units.

Code: Select all
method         GN     Fata M.
-------------------------------------------------
Backtrack      49     191      arbitrary units
Algorithm X'   46     129      arbitrary units


Like you, I now suspect there is something odd about the puzzle(s). Is there an SE rating?
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby champagne » Tue Sep 16, 2008 10:31 am

Hi Allan,
Allan Barker wrote:Champagne, it will take a couple of days to get images and diagrams on to my website and will let you know when I do.

No probem, I have first to understand your process.
Allan Barker wrote:
Code: Select all
method         GN     Fata M.
-------------------------------------------------
Backtrack      49     191      arbitrary units
Algorithm X'   46     129      arbitrary units


Like you, I now suspect there is something odd about the puzzle(s). Is there an SE rating?


I have a simlar indicator with my "count" time in milliseconds. I keep it in my stats and I publish it, but up to now, I have no visual correlation with the processing/printsize data. It remains true that a puzzle having a high "counting time" is normally a very hard puzzle.
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

Previous

Return to Advanced solving techniques