|
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 |
|
|
|
|
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
|