Pattern Based Sudoku Solving Algorithms (part Β)

I wonder if I ever get serious and finish my projects or any for that matter. Last time I presented a fairly complicated algorithm idea about a more humanized based Sudoku solver instead of the brute force ones that applications usually utilize.

Someone can argue, what’s the point of creating a fairly complicated solution to a simple problem that can be solved in just a few seconds using brute force.

Well Because its fun. So, here you go, another made up Sudoku solving algorithm

This time, I though, that it would be interesting to combine my geometrical and topological background, as well as some GIS based algorithms that we have developed over time.

The first implementation cannot solve all Sudoku puzzles but it can do fairly well in medium strength ones like this one

input

output

(more…)

metric information from camera ray reconstruction

As explained in a previous article (simulating a camera) (which is basically converting 3d objects to 2D projective geometry, with specific camera parameters) is one thing, but getting metric information out of a photograph is totally another. There are several ways of achieving this. You can either use a digital terrain model and one oriented image or a pair of oriented images (stereoscopic). In this article I am going to focus on a stereoscopic “technique”. Some “techniques” require good mathematical knowledge and skills while others are a bit more graphical (meaning you can actually imagine the solution and even graphically depict it).In this article I try to explain how to compute a point’s 3D space coordinates, from two images using camera ray reconstruction.

(more…)

An implementation of knight’s tour algorithm written in javascript & html5

A knight’s tour is a sequence of moves of a knight on a chessboards such that the knight visits every square exactly once. The knight’s tour problem is an instance of the more general Hamiltonian path problem in graph theory. we use the Warnsdorff’s rule “an heuristic algorithm”. We move the knight so that we always proceed to the square from which the knight will have the fewest onward moves. When calculating the number of onward moves for each candidate square, we do not count moves that revisit any square already visited. It is, of course, possible to have two or more choices for which the number of onward moves is equal. Below we can see the piece of code where the chessboard created using html5 and algorithm’s implementation in javascript. The algorithm chooses the square where the knight has the minimum value of possible moves. This is not the best approach because there are cases that the puzzle doesn’t have a solution as we can see at this paper. In a next post i’ll try to solve the problem. The knight’s tour has been tested in mozzila firefox and google chrome.

(more…)

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…)