Pattern Based Sudoku Solving Algorithms (part A)

It is no secret that I love puzzles. Depending on the mood and period of my life, I find myself stuck with a certain kind of puzzles. Sudoku,among others, is naturally one of them and since I am fascinated with logic, it was bound, at some point, to check out what approach most programmers take in solving such a problem.

Most sudoku solving algorithms out there just “do” the job. Meaning they are mostly recursive and back-tracing solutions (like dancing links) rather than a more natural human approach.

Now whats the point in solving such a relatively simple problem without using such techniques. The point is that DLX techniques cannot produce a straight forward solution, I mean one that the filling sequence could fool someone that it wasn’t solved by a computer.

So I thought why not try to write some code based on how I think while solving a puzzle. Also Iam not allowing the algorithm to take notes and by notes I mean to pre-calculate every possible number that might correspond to each empty space.

My Solution so far is based on 3 Patterns and can solve most sudoku puzzles with a degree of difficult up to 7, 10 being the hardest.

There will be many more posts on this topic, in the near future…and probably some results concerning performance issues as well as a bit of code.

Here is a draft flowchart of the first Thinking Pattern
(more…)