The New Sudoku Players' Forum

[Ruud]

Each test you choose involves a cost (computer time).

I would agree with you when we were looking for the fastest way to solve a sudoku. However, this has never been my intention. What I am looking for is the shortest solving path that can be presented to a human player in the form of a series of hints or a solver log. The more complex sudokus (see my example) tend to produce very long chain reactions in the solver's log. (see rubylips' reply, I have not posted my log entries yet, they are too embarrassing).

If the cost to eliminate 7 candidates is big and the relative cost of eliminating 2 candidates is very small, then the 2-candidate test should be preferred.

For simplicity, yes. For finding the shortest path, we should look at the after-effects of both techniques. If the 7 eliminations break the puzzle into singles only, that path is shorter than the easier 2-candidate path that requires a more advanced technique before it finally breaks.

Who would do anything else except perfrom [SIC] eliminations based on singletons when faced with a new puzzle.

We are not looking at those difficulty levels here. Many solver programs can handle puzzles with singles only. However, once some T&E-based methods are required, results show greater variation. My aim is to find the shortest route to the solution, with human-style techniques only.

The last 2 points about ineffective test are also not relevant to the problem at hand. They are indeed relevant for solver-programmers and have been discussed in-depth on the sudoku programmers forum.

I do agree it is complicated.

"It is a strange fate, that we should suffer so much fear and doubt over so small a thing". (JRR Tolkien)

Ruud.

[ronk]

By way of comparison, my non-published solver uses the following blend of techniques for your example:
22 Givens
9 Hidden singles (total)
50 Naked singles (total)

7 Line-Box interactions (locked candidates) (9 eliminations)
2 Naked pairs (5 elims)
0 Hidden pair
0 Hidden Triple
0 X-Wing
0 Coloring check
38 forward implication chain eliminations

Hi Ruud,

I made a simple change to the forward implication function to first guess as true those candidates in bivalued cells, then trivalued cells, etc. ... rather than candidates in the "first cell", i.e., scanning each cell of each row.

I did so on the theory that eliminations in bivalued cells would lead to placements in turn leading to a quicker solution of a puzzle. But I was shocked to see the eliminations due to forward implication drop from 38 to 9.

As we discussed earlier, this new algorithm may now be stumbling upon a magic candidate sooner and could thus be meaningless. I'll have to figure out an easy way to evaluate the two approaches over a large number of puzzles ... which should tend to "neutralize" the effect of magic candidates.

[Ruud]

Hi Ron,

I'm not surprised too see that significant drop.

Currently, I'm assigning priority on the following properties:

1. Smallest size of smallest constraint;
2. Largest sum of all 4 constraint sizes;

By using the smallest constraint size, it picks a bivalue or bilocation candidate first, then a trivalue/trilocation, etc.

The second priority ensures that the largest number of other candidates are eliminated. Make sure you perform this count on the constraints for the remaining candidate, not the one you are eliminating. I made this mistake and it was very hard to detect it....

On the topic of magic candidates,

It is not bad to use magic candidates, as long as you do it on purpose. I have not had too much time lately to further optimize the solver, but I still think that you should keep track of magic cells and assign a higher priority on elimination of those candidates that trigger a magic cell.

I wonder how BUG's, Nice Loops and ALS affect the optimal solving path.

Has anyone who implemented these techniques tried them on the samples in this topic?

Ruud.

[tarek]

Hi everyone,

My solver's take on the puzzle at the start was:

63 single eliminations
6 Hidden singles
3 Box-line interactions (7 eliminations)
1 Naked double
2 Hidden doubles (3 eliminations)
1 Hidden triple
2 X-Wings (3 eliminations)
7 Forcing implications (13 eliminations)
1 Nishio
4 simple guesses

needed to crack the puzzle in an HOUR (well, it felt like an hour)

It seems like on some occasions if you spot an XY wing at the start, single elimination follow to a complete solution without the need to go through Box-line eliminations & doubles.....

Now you could choose either the number of non single elimination steps required to crack it (The most elegant economic way) or to TIME your solution.

I have read elsewhere that one way to analise this is to systematically swap the nesting techniques & compare results (Steps or Time or both) for each nesting sequence. The results (over many different puzzles) would tell you which nesting sequence would give the optimal pathway (an average or whatever statistical method)

Can we try that with this puzzle & see what was the best result......