Sudoku Solver

There are many ways of solving Sudoku programmatically. The first attempt would be to replicate what people do. In any empty cell list all possible candidates. If there is only one candidate then fill the cell with that candidate. The dual of this procedure is: if in any row or column or box there exists a number that can go into only one cell then fill that cell with that number. Mathematically speaking there is a bipartite graph linking cells to numbers. If there exists a node with only one arc then that arc ties the source and destination.

But a more brute force technique would be: Consider the first empty cell. Fill it with smallest candidate number based on the existing partly filled Sudoku. Then consider the next cell until all cells are covered. If there is a cell that has no candidate then back track; replace the last filled cell with the next candidate solution. If that cell has run out of candidates back track another step and so on.

Turns out that this ‘crude’ algorithm is only less than 200 lines of C++ and has worked for the small sample set that I tried. Check it out at The Sunday Programmer

Advertisements

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Software Puzzle and tagged , . Bookmark the permalink.

2 Responses to Sudoku Solver

  1. Pingback: Breadth First Search | The Sunday Programmer

  2. Pingback: No Raw Pointers | The Sunday Programmer

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s