Home > Uncategorized > Yet another Sudoku solver

Yet another Sudoku solver

I revisited the dancing links algorithm for solving Sudokus. My previous implementation and post can be found here. This time I used C++. The most important difference, however, is that I realized that it is easy, and faster, to build the sparse matrix directly. Last time I created a dense matrix first.

The code repository is here; https://bitbucket.org/d95danb/cppdlx.

This time, I decided to also measure performance, using the same approach as attractivechaos in the blog post An incomplete review of Sudoku Solver Implementations. The author uses 20 really hard Sudokus that are solved repeatedly 50 times.

The bench marking machine I used for the test was equipped with a AMD Athlon 64 X2 Dual Core Processor 5000+ (2.6GHz) which Windows rated index 5.6 on the scale of CPU performance (5.1 considering the entire machine).

Given this, in release build, the resulting time was about 1.2 seconds which competes well with the other Sudoku solvers from the article.

Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: