View previous topic :: View next topic |
Author |
Message |
| Seaplusplus
| Joined: 23 Mar 2008 | Posts: 12 | : | | Items |
|
Posted: Thu Jun 26, 2008 8:34 pm Post subject: C++ brute force solver |
|
|
Hey. Here's a simple sudoku solver programmed in C++. I was told that there is something wrong with the brute force, and it would not give all the solutions. I was under the impression it would give all possible solutions when i made it. I've put it through testing myself and it seems to work correctly, but if you could have a look and see if you can find an error, It would be very much appreciated. For example, It would be great if someone had a sudoku with, say, 100 solutions. If you want you can give me the puzzle and I will test it myself.
It basically creates a double linked list of all the empty cells and systematically goes through them all adding in the numbers that are allowed until the grid is complete. If no numbers are allowed in a cell, the previous cell that was changed is inremented.
relevent code (brute force part) - http://rapidshare.de/files/39840754/Source1.cpp.html
exe - http://rapidshare.com/files/125246600/Sudsolver.rar.html feel free to give it a test drive. It does simple logic, then moves on to brute force! |
|
Back to top |
|
|
| Seaplusplus
| Joined: 23 Mar 2008 | Posts: 12 | : | | Items |
|
Posted: Fri Jun 27, 2008 6:53 pm Post subject: |
|
|
I tried this puzzle
Code: |
000|004|500
000|800|000
702|003|900
-----------
508|000|060
300|000|007
090|000|201
-----------
001|600|000
000|005|000
004|290|000
|
My solver found 1242 solutions. Could someone verify this number?
Thanks |
|
Back to top |
|
|
| Jean-Christophe
| Joined: 19 Mar 2006 | Posts: 126 | : | Location: Belgium | Items |
|
Posted: Fri Jun 27, 2008 8:30 pm Post subject: |
|
|
Seaplusplus wrote: | My solver found 1242 solutions. Could someone verify this number? |
Same count for my soft JSudoku _________________ Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes. |
|
Back to top |
|
|
| Seaplusplus
| Joined: 23 Mar 2008 | Posts: 12 | : | | Items |
|
Posted: Sat Jun 28, 2008 12:30 am Post subject: |
|
|
yes thank you. I found the problem, was not to do with brute force part actually. Just looked like that was the problem from the error. |
|
Back to top |
|
|
| humble_programmer
| Joined: 27 Jun 2006 | Posts: 69 | : | Location: Colorado Springs, USA | Items |
|
Posted: Sat Jun 28, 2008 4:09 pm Post subject: |
|
|
If you visit Ruud's Sudopedia (http://www.sudopedia.org/wiki/Main_Page) you'll find a set of test cases for Sudoku solvers that I contributed some time ago. Under "Invalid Test Cases" (http://www.sudopedia.org/wiki/Invalid_Test_Cases) you should find starting grids with a known number of multiple solutions. Here are a few more that I use in testing my own code:
3,673 solutions:
Code: | ...3.65..8..5......1.....4.9...8..2...........4..6...1.5.....1......9..2..61.8... |
957, 263 solutions:
Code: | 536.2.9....8...............6..285..9...9.3...8..761..4...........4......2.1.....7 |
50,044,975 solutions:
Code: | ....69.3...1.......6......24.5..3..........5..16.....7....9...........711........ |
(Be careful about the last one...it can take a while, even for a fast solver!) _________________ Cheers!
Humble Programmer
,,,^..^,,,
www.humble-programmer.com |
|
Back to top |
|
|
|