Sunday, August 15, 2010

Much to do and KSudoku again...

There is not much time to work on KSudoku recently. But I think I found the reason why generating some puzzles takes forever. And maybe it will benefit from an idea that might also improve difficulty of the puzzles.

At the moment I'm relocating. I'm moving to my first own apartment together with my girlfriend. Until now I stayed with friends or lived in dorms. So I'm looking forward to how it will be. At the same time there is much work to do at my job as we are approaching the release of our project. And the begin of writing my bachelor thesis is approaching. So not much time left for developing on KDE.

KSudoku is currently hardly of any use. Games are much to easy to solve and some games couldn't be even generated. The reason for freezing during generation of Jigsaw-puzzles is a rather simple one. And very hard to solve at the same time.

KSudoku generates puzzles by solving an empty one. As long as it can't solve with logic it tries to insert values at random positions. If it detects that one such value makes the puzzle unsolvable it tries some other value. In case of Jigsaw puzzles entering two values can make them unsolvable.

This game has no solution. Without knowledge of Jigsaws special rules it is difficult to tell that. Once you know the rule this particular problem has an easy solution. I leave it to you to find out which one. But this solution would not apply to other similar problems.

A better way would be to not try all possibilities when testing a branch but going back to earlier values when the errors are rather similar. Another improvement would be to reduce the cost of branching. As branching is a costly operation and there is much room for improvement this would make testing more branches in the same time possible. Lookahead branching would be another improvement that would also increase difficulty of generated games. Instead of testing a complete random branch the solver would first analyze the changed introduced with a branch and select the most promising branch to test it.

And last but not least is there the possibility to improve the logical part of solving. Combining some constraints would make it possible to generate new constraints. This constraints would eliminate many of the branches so that the basis for the exponential trial-and-error-solving would shrink.

2 comments:

Anonymous said...

Wouldn't it be an option to use a generic sat solver ? That way you could save yourself the effort of having to write your own custom solution while still get a quite decent performance

simi said...

I think i found a better solution, starting from a completed/solved configuration use permutation of the lines and columns to find other configurations. What do you think? I can help implement it