Well, hello to all of you, kind blog readers, whoever and wherever you are. This is my first post, or making reference to what observational astronomers say when a new telescope captures its first image ever, this is my first light.
I think Luis already mentioned the main points concerning myself. I've been fascinated with Physics, Astronomy and Computers since I was very little, so getting into numerical astrophysics was an inevitability of fate, it seems. In case I seem too geeky, I should note that I also enjoy movies, music, videogames and drinking beer/tequila like there's no tomorrow.
My current research is focused towards numerical models of DEM L316, a pair of supernova remnants in the Large Magellanic Cloud that were caught in action, ie: two supernovas that might have exploded near to each other and thus may now be colliding.
-
Now, time for some Sudoku! For those of you who don't know, Sudoku is a simple number game, where one must fill the blanks in an incomplete 9 x 9 number grid, following a simple rule: a number may only appear once in each row, each column and in each of the nine 3 x 3 blocks of the grid.
I spent most of my afternoon writing a Sudoku solver. Since I'm a bit rusty with my programming skills, I thought it'd be a good exercise. The program is written in C++ and I've compiled it under SuSE 10.3 (which I've just installed on my laptop and works wonderfully).
You can download my Sudoku solver here.
It's a gzipped tarball. I've also included a binary compiled in SuSE 10.3. In order to compile the source in your own distro, if you have the GNU C++ compiler just type "g++ -o sudoku sudoku.cpp". The grid to solve is entered in the data file sudoku.dat, which should be in the same directory as the binary. I've included the hardest grid I've found (for my solver) as example; it takes 605,484 trials to solve it.
The algorithm behind the program is simple. It's a brute-force recursive algorithm. This means my algorithm solves Sudoku by trying a valid number in the first empty position, then trying a valid number in the next grid position, then the next, etc ... all this done through a recursive function. When the function finds it cannot place a number in a particular position, it goes back to the last grid position, and tries the next valid number there... again, all this done recursively.
In the end, it works very well and fast enough (despite being an exhaustive algorithm). It takes well under a second on my C2D T7100, 2GB RAM laptop to find the solution to any grid I've fed the program. The program is nice since it makes use of recursion, which is a powerful feature of programming languages. As the creator of Ghostscript, L. Peter Deutsch, put it:
I think Luis already mentioned the main points concerning myself. I've been fascinated with Physics, Astronomy and Computers since I was very little, so getting into numerical astrophysics was an inevitability of fate, it seems. In case I seem too geeky, I should note that I also enjoy movies, music, videogames and drinking beer/tequila like there's no tomorrow.
My current research is focused towards numerical models of DEM L316, a pair of supernova remnants in the Large Magellanic Cloud that were caught in action, ie: two supernovas that might have exploded near to each other and thus may now be colliding.
-
Now, time for some Sudoku! For those of you who don't know, Sudoku is a simple number game, where one must fill the blanks in an incomplete 9 x 9 number grid, following a simple rule: a number may only appear once in each row, each column and in each of the nine 3 x 3 blocks of the grid.
I spent most of my afternoon writing a Sudoku solver. Since I'm a bit rusty with my programming skills, I thought it'd be a good exercise. The program is written in C++ and I've compiled it under SuSE 10.3 (which I've just installed on my laptop and works wonderfully).
You can download my Sudoku solver here.
It's a gzipped tarball. I've also included a binary compiled in SuSE 10.3. In order to compile the source in your own distro, if you have the GNU C++ compiler just type "g++ -o sudoku sudoku.cpp". The grid to solve is entered in the data file sudoku.dat, which should be in the same directory as the binary. I've included the hardest grid I've found (for my solver) as example; it takes 605,484 trials to solve it.
The algorithm behind the program is simple. It's a brute-force recursive algorithm. This means my algorithm solves Sudoku by trying a valid number in the first empty position, then trying a valid number in the next grid position, then the next, etc ... all this done through a recursive function. When the function finds it cannot place a number in a particular position, it goes back to the last grid position, and tries the next valid number there... again, all this done recursively.
In the end, it works very well and fast enough (despite being an exhaustive algorithm). It takes well under a second on my C2D T7100, 2GB RAM laptop to find the solution to any grid I've fed the program. The program is nice since it makes use of recursion, which is a powerful feature of programming languages. As the creator of Ghostscript, L. Peter Deutsch, put it:
To iterate is human; to recurse, divine.As is to be expected, the greater the number of blanks to fill, the more trial number placements the program must do to achieve a solution. However, there is no clear correlation between the reported difficulty of a particular grid and the trials needed by my code to solve it, other than the fact that harder puzzles usually have a larger number of empty squares to fill.
2 comments:
Welcome aboard!
I actually remember solving the soduku puzzles of the newspaper while taking the bus to school.
By the way, have you tried the Hannoi towers problem? Seems to be a fine iterate/recursion situation.
But can it solve sudoku in decamillesimal system instead of decimal?
Post a Comment