Exotic game and new solution technique...

Sven Geier

All the things a geek needs: physics, medical imaging, Sudoku:

http://www.news.cornell.edu/stories/Feb06/Elser.sudoku.lg.html

thought this might be the right place to pass this on...

Soultaker · Posted: Sat Mar 04, 2006 2:42 pm Post subject:

Thanks for sharing that!

Unfortunately, articles like that are why I hate journalists who write about scientific (or generally 'difficult') topics. Ofcourse, it doesn't help that I know nothing about X-ray diffraction, but the only thing I can infer from the article is that Elser has developed a constraint solver.

How and if this algorithm differs from existing constraint logic programming systems does not become clear. Seeing how much work has already been done in this area, I doubt his algorithm is novel; it's probably just the application to the problem of X-ray imaging. However, the article suggests that is algorithm is more general. I'd be interested in reading more about it.

At any rate, the Sudoku puzzle he generated is nice, but not much special. It is valid; it has a unique solution that can be found in about three seconds with a traditional algorithm. The name to look for is Andrew Dickson White.

gsf · Posted: Sat Mar 04, 2006 3:47 pm Post subject:

eclark · Posted: Sun Mar 05, 2006 12:16 am Post subject:

gsf as always your solver speed is exceptional

antony

Hi,
Here is a free Java implementation of the algorithm:
http://jpboucher.free.fr/antony/ElserSolver.zip

The limitations of the algorithm with Sudoku are that:
- it does not prove solution unicity
- never stops if the grid is unsolvable
- the 'beta' parameter is critical to the convergence (has to be finely tuned)
- slower than solving by logic for grids that can be solved by logic

Advantages:
- can solve grids regardless of backtracking issues
- algorithm simplicity
- works for all sizes (I tried up to 36x36 cells)

Have fun,
Antony

Soultaker · Posted: Sat Mar 25, 2006 4:13 pm Post subject:

Hey Antony! That sounds interesting; if the algorithm is indeed simple, could you explain how it works?

antony · Posted: Sat Mar 25, 2006 7:40 pm Post subject: explanations

Here is an short explanation of the algorithm and how I implemented it. I believe there are other ways, which may be more efficient. For the sake of simplicity, let's assume the grid is 9x9 cells.

The grid is represented internally by a 3D array: row, column, digit. I.e., map[r][c][d] is =1 if the solution has the digit d in the cell at row r and column c. map[r][c][d] is =0 if the digit d is not in the cell r,c.

Hence you can interpret map[r][c][d] as "presence of digit d in cell r,c".

Until the solution is found, there are wrong values in map[r][c][d] (there can be 0, 1, but also any real number). Elser's algorithm will modify the values iteratively, until the map 'converges' (stops changing from iteration to iteration). This fixed map itself does not obey Sudoku constraints, but the solution is found by transforming the fixed map with a final, special iteration.

Now, what is an iteration? It transforms the map by applying and composing two 'constraint operators', with a few linear combinations. There is a constant involved, 'beta', that defines how much (and how well) the map changes.

A constraint operator transforms the map so that it then obeys the constraint.
Operator: map breaking the constraint ---> map obeying the constraint

I divided the rules of sudoku into 2 sets of constraints. If a map obeys both, then it is a solution ('the' solution, if it is unique.)

First set of constraints: "the grid obeys clues, and values are either 0 or 1."

Corresponding operator: "in cells where we have a clue, set one value to 1 and the other eight values to 0. In cells where we don't have a clue, set values>=0.5 to 1 and values <0.5 to 0."

Second set of constraints: "there is only one of each digit in every row / column / block, and only one digit in each cell".

Operator: it is important to note that, to enforce this constraint, we are allowed fractional values. Indeed, the constraint that "values must be 0 or 1" is enforced by the previous operator. This second operator is NOT bound by it. Hence this operator acts like this:

Soultaker · Posted: Sat Mar 25, 2006 11:15 pm Post subject:

Thanks for the explanation (and for your code, which is very tidy)!

One thing I wonder about is how you can guarantee to find a solution if one exists. When I test it against the 'top 1465' problemset (magictour.free.fr/top1465) it produces an invalid solution after 1 million iterations for about 2% of the problems. Would the algorithm be stuck indefintely in these cases, or would it eventually find the solution given more iterations?

From your explanation and code, it seems that there is no backtracking involved and no randomization after the initialization of the map; how do you ensure eventually progress will be made?

antony · Posted: Sun Mar 26, 2006 1:47 am Post subject:

I stop the loop after 1000000 iterations, considering the algorithm does not reach a solution.

Maybe it can solve the 2% remaining problems with a better tuned beta parameter, or different constraint operators. Elser did not publish his, so I tried and designed my own.

Beta has a big influence on the performance, i.e. for some grid sizes, 0.47 is much better than 0.45 or 0.50.

I'm not sure if the algorithm is really a good choice for sudoku: solutions have to strictly obey the sudoku rules. This need for perfection may be out of reach of Elser's algorithm in some cases. On the contrary, in biological imaging, constraints are looser: the output image does not have to be noiseless, as long as it is sharp and clear.

It is interesting however to see grids solved by iteratively resolving all constraints at once.

antony · Posted: Mon Mar 27, 2006 12:57 am Post subject:

I just improved the performance by tuning one of the parameters (gamma2).

On your suggestion, Soultaker, I also reset the grid once and a while when the algorithm has trouble with it. It should solve all the 1465 pbs now Surprised

Soultaker · Posted: Mon Mar 27, 2006 1:10 am Post subject:

Nice!

I agree with your previous comment though: this algorithm is probably not the best choice for solving Sudoku, but I must admit it's a pretty cool idea and for an algorithm without logic or backtracking it works very well.