Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 DLX and Sudoku Solver
Index -> Programming, C++ -> C++ Submissions
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
bbi5291




PostPosted: Tue May 26, 2009 4:07 pm   Post subject: DLX and Sudoku Solver

Here's my implementation of Knuth's "Algorithm X with Dancing Links", or DLX for short, for solving the exact cover problem. This is in the file dlx.h. The file dlx_driver.cpp is, as its name suggests, a driver for the header, reducing Sudoku to exact cover.

To use the Sudoku solver, simply input 81 cells to standard input. Digits 1..9 represent givens (as one would expect). The digit zero and the period represent blank cells. All other characters are ignored. Thus, input is accepted in several different formats. In most cases you can simply copy-and-paste into the console what you find online. (Spaces are ignored, not treated as placeholders. This means if spaces are used as placeholders, this won't work properly. On the other hand if I treat spaces as placeholders, leading and trailing spaces cause problems, which IMHO is worse.)

Solutions are printed to standard output as 9x9 grids of digits - all possible solutions are printed, as they are generated one by one as the recursive algorithm proceeds. Each solution is followed by a blank line. If no solutions are found, nothing will be printed.

Also, before I start getting attacked over my misuse of templates, choice of language, poor commenting, and overall sloppiness, remember that I'm primarily a computer science enthusiast, not a software engineer.

Tested and working on g++ 4.3.2, although it shouldn't cause problems with other compilers.



dlx_driver.cpp
 Description:

Download
 Filename:  dlx_driver.cpp
 Filesize:  1.31 KB
 Downloaded:  1032 Time(s)


dlx.h
 Description:

Download
 Filename:  dlx.h
 Filesize:  5.84 KB
 Downloaded:  1263 Time(s)

Sponsor
Sponsor
Sponsor
sponsor
saltpro15




PostPosted: Tue May 26, 2009 8:37 pm   Post subject: RE:DLX and Sudoku Solver

wow... this is very impressive. I haven't read the full code yet, but I read that wiki and well, wow...
bbi5291




PostPosted: Tue May 26, 2009 8:45 pm   Post subject: Re: DLX and Sudoku Solver

Actually Wikipedia just has a tendency to formalize mathematical concepts because, well, that's the way they're supposed to be treated. But exact cover is not nearly so difficult as it might seem - given a matrix of 1s and 0s, select a subset of rows to form a new matrix with exactly one 1 in each column. (My code actually removes empty columns; this is not strictly necessary as empty columns actually mean that there is, obviously, no solution to the exact cover problem, but such empty columns are a relic of the algorithm used to fill in the known values.)

The code is intended to show off how fast it is, not how smart I am, or how good I am at coding Razz
Display posts from previous:   
   Index -> Programming, C++ -> C++ Submissions
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 3 Posts ]
Jump to:   


Style:  
Search: