The New Sudoku Players' Forum

[pjb]

May I please draw your attention to a new sudoku solver and tutor. This one is fully in javascript, and fully interactive, so any of the available strategies can be tried in any order. It can solve any sudoku I have come across (including 'golden nugget', 'easter monster', etc) using the same hierarchy of techniques. These techniques, in my opinion at least, are fully logic based.

The program offers basic techniques up to ‘fish’, then offers a collection of advanced techniques. There is a full implementation of POM (a much neglected technique) and ALSs. Several varieties of chains are enabled.

The program can be accessed at http://www.philsfolly.net.au

It has what I believe are new approaches to solving the harder puzzles. For the very hard ones that aren’t solved using ‘normal’ techniques, I have developed 3 techniques based on

1. Single digits – any candidate digit can be either true or false
2. Units – the candidates in a unit (ie row, column or box) can have many combinations of the 9 digits, but only one is true
3. Patterns – A given digit may have many (even thousands) of possible patterns, but only the one in the solved puzzle is true, all the others are false

In each of these 3 cases, if the digit (or digits) is hypothesized to be true, and the logical consequences of doing this are examined, then a contradiction may be discovered. The methodology for finding contradictions is fully explained in the help items.

Single digits:
1. If the hypothesis that a digit is true is correct, then no contradiction will occur
2. If the hypothesis that a digit is true is incorrect, then
a. If there is no contradiction, no conclusion can be made
b. If there is a contradiction, then the hypothesis that the digit is true must be incorrect, and the digit can be eliminated

Units:
For a chosen unit, all valid combinations are obtained. All nine digits for a given combination are hypothesized to be true, and if a contradiction results then that combination is removed from the total. At the end of the process, the remaining combinations are transformed back into the unit, which may or may not have reduced number of candidates.

Patterns:
For a chosen digit, all patterns are generated, and tested as above one at a time, and if a pattern causes a contradiction that pattern is removed from the total. After all patterns have been tested, the remainder are transformed into a 9x9 grid and compared to the actual Sudoku. If there is a cell that all remaining patterns include, then that cell can have the value of the chosen digit. If there are cell(s) which none or the remaining patterns pass through, then the digit can be removed from these cells. (This is the same process used in the POM analysis employed earlier in the program).

The Killer Method
If the above are not enough (as is the case in the very hardest puzzles) some something extra is needed. If one generates an array of all instances of a digit occurring twice in a unit (ie pairs), then one can make one of the pair true, then a second single digit true, and see if there is a contradiction. If there is, then can make the other of the pair true, and the same second digit true, and if there is again a contradiction, then the second digit must be false and can be eliminated. This is because one of the pair has to be true, so the contradiction must be due to the second number. This process can be enabled for triples and even quads. (in very hard puzzles there aren’t many pairs, so triples are initially needed).

This same approach has been enabled for both unit and patterns. The patterns approach seems the most powerful, and most difficult patterns can be solved using this alone by repeated application. The progress of these methods is fully outputted into a text box so the logic can be examined.

This is early days, and the program may have bugs or produce errors. I would be grateful if you took into account that I am an amateur programmer, and not be too harsh with criticism. BTW, please don’t use IE. Chrome is at least 10 times faster and much preferred, Firefox almost as good. Safari is hopeless.

[SudoQ]

Hi pjb,

What I have seen so far looks very interesting.
I am looking for programs that meet the following specification:
* Can solve all 9*9 puzzles.
* Can create fairly short solutions.
* Can create steps that a man can follow.
* Can do this fairly quickly.
* To be able to do this without any interference from humans.

I would now like to know two things about your program:
* Is it possible to replace the dialogues (that hides the puzzle) with a step log in the window at the bottom on the page?
* Is it possible to let the program choose the appropriate method for each step?

/SudoQ

[pjb]

Hi pjb,

What I have seen so far looks very interesting.
I am looking for programs that meet the following specification:
* Can solve all 9*9 puzzles.
* Can create fairly short solutions.
* Can create steps that a man can follow.
* Can do this fairly quickly.
* To be able to do this without any interference from humans.

I would now like to know two things about your program:
* Is it possible to replace the dialogues (that hides the puzzle) with a step log in the window at the bottom on the page?
* Is it possible to let the program choose the appropriate method for each step?

/SudoQ

Hi SudoQ

First question: Yes it would be possible. However, my starting concept was to give the user the ability, by stopping the execution, to study each step before the program runs to some endpoint. Eventually I plan to have all output echoed in the output box. The alert box can be dragged off the grid (if you can't you're in the wrong browser - I strongly recommend Chrome).
Second question: I agree it would be good to have this as an alternative option. I do like however being able to go back and try different techniques manually. One thing I don't like about some solvers, eg SE, is that they choose the next move without any user control. I thought I would like to be different. But being able to run it either way would be the ideal.

pjb

[ronk-Moderator]

pjb, always quoting an entire post is the hallmark of a lazy poster. Please quote selectively that which is relevant to your response.

[SudoQ]

The alert box can be dragged off the grid (if you can't you're in the wrong browser - I strongly recommend Chrome).

Ok, on this occasion, I used Mozilla ...
I also think it would be easier to follow the steps if you showed cell positions in the standard format 'r1..9c1..9'.

However, my starting concept was to give the user the ability, by stopping the execution, to study each step before the program runs to some endpoint.

I agree that it's good that you can take one step at a time.
It's also good that you then can choose which method you want to try.

However, in order to be able to see what solution your program prefer,
and to see how long it takes to solve an entire puzzle,
it would be nice to also have a 'Solve puzzle' button!

/SudoQ