FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    My first Sudoku Alg. doesn't work? Help please          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message Divine Love Joined: 22 Dec 2008 Posts: 2 : Items Posted: Mon Dec 22, 2008 7:53 am    Post subject: My first Sudoku Alg. doesn't work? Help please Hi, everone I am new to this forum and amazed to see that there is a seperate sub-forum dedicated to Sudoku as I have been struggling with this problem lately. I was required by my AI prof. to write a Sudoku solver. I used Brute Force alg. with back tracking but my algorithm seems to take a loooooooooong time to solve the sudoku (many hours). I don't know what's wrong with my code. A friend of mine has written a code which is similar to mine except has a pruning condition that hugely decreases the number of iterations but he never tells me how the pruning works. Here is my code: Code:  void SolveTheSuduko()         {             for (int i = 0; i < 9; i++)             {                 for (int j = 0; j < 9; j++)                 {                     if ((suduko[i, j].Rigid == false) && (suduko[i, j].Visited == false))                     {                         for (int choice = 0; choice < suduko[i, j].ValidChoices.Count; choice++)//Tests for all the valid values                         {                             if (IsValidChoice(suduko[i, j].ValidChoices[choice], i, j))                             {                                 suduko[i, j].Value = suduko[i, j].ValidChoices[choice];                                 suduko[i, j].Visited = true;                                 SolveTheSuduko();                                 if (IsSolved())                                 {                                     Finilize();                                 }                             }                         }                         suduko[i, j].Value = 0;                         suduko[i, j].Visited = false;                     }// end of first if                 }             } } I'd really appreciate your help! Thanks in advance! Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Mon Dec 22, 2008 9:50 am    Post subject: Re: My first Sudoku Alg. doesn't work? Help please Divine Love wrote: I was required by my AI prof. to write a Sudoku solver. I used Brute Force alg. with back tracking but my algorithm seems to take a loooooooooong time to solve the sudoku (many hours). I don't know what's wrong with my code. A friend of mine has written a code which is similar to mine except has a pruning condition that hugely decreases the number of iterations but he never tells me how the pruning works. Well, think about this: if the puzzle contains, say, 5 as a clue in the first row, is it necessary to test all the other cells in the first row for 5? Regards, Mike Metcalf Back to top Divine Love Joined: 22 Dec 2008 Posts: 2 : Items Posted: Mon Dec 22, 2008 2:02 pm    Post subject: Thanks for reply. Of course not. My algorithm doesn't test for that values. The way my algorithm works is as follows Every cell is an object that contains a property named Value, a list named ValidChoices, and a property called Visited to indicate whether the cell has been visited before or not First I fill each cell's ValidChoices list by all the valid numbers for that cell (numbers that doesn't violate the intial formation of hints). Then I start filling each cell's Value by a valid value from its ValidChoices list and then test if it doesn't coincide with the newly created clues as the algorithm progress. If no problem I continue to the next field and fill it with a value from its ValidChoices list. In case all of the ValidChoices of a cell are in coincide with the other cells the algortim moves one step back and choose the second value from the previous cell's ValidChoices list. I think it's exactly how a Brute Force algorithm works and still more optimized as it doesn't test for values which are the same as a vertical, horizontal or regional hints. Please correct me if I'm wrong. Back to top m_b_metcalf Joined: 13 Mar 2006 Posts: 210 : Location: Berlin Items Posted: Mon Dec 22, 2008 3:44 pm    Post subject: Divine Love wrote: Thanks for reply. Of course not. My algorithm doesn't test for that values. The way my algorithm works is as follows Every cell is an object that contains a property named Value, a list named ValidChoices, and a property called Visited to indicate whether the cell has been visited before or not First I fill each cell's ValidChoices list by all the valid numbers for that cell (numbers that doesn't violate the intial formation of hints). Then I start filling each cell's Value by a valid value from its ValidChoices list and then test if it doesn't coincide with the newly created clues as the algorithm progress. If no problem I continue to the next field and fill it with a value from its ValidChoices list. In case all of the ValidChoices of a cell are in coincide with the other cells the algortim moves one step back and choose the second value from the previous cell's ValidChoices list. I think it's exactly how a Brute Force algorithm works and still more optimized as it doesn't test for values which are the same as a vertical, horizontal or regional hints. Please correct me if I'm wrong. Well, that all seems correct. A further optimization is to visit the cells in order -- fewest choices first, most choices last -- but I can't see how not doing that makes your code take hours. I recommend that you test it with a puzzle that is nearly filled and write out each step that it takes. Regards, Mike Metcalf Back to top Adak Joined: 27 Feb 2008 Posts: 87 : Items Posted: Thu Dec 25, 2008 9:06 am    Post subject: I don't see anything about trying to resolve simple naked singles (in Row, Column, or BoxOfNine). You may be quite smart, but your program is quite dumb. If you're just searching through the entire possible search space for the puzzle grid until you find the answer, that sounds very slow, indeed. You want to resolve singles, both naked and hidden, first. Nothing is better, overall, in reducing your number of candidates. That, in turn, will speed up your brute force solving. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming sudoku All times are GMT Page 1 of 1   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron