|
| View previous topic :: View next topic |
| Author |
Message |
| bhavina
| | Joined: 23 Feb 2008 | | Posts: 6 | | : | |
Items |
|
 Posted: Sat Mar 29, 2008 1:07 pm Post subject: few queries in solving sudoku |
 |
|
Hey, just a few queries: if using just a simple backtracking algorithm to solve sudoku puzzles, how do I implement it so that each blank cell has all the possible values it can have and then a cell that has only one in its domian is assigned and then the cell with the smallest domain is assigned first etc? Would this entail dynamic variable ordering or static? Is that brute force just starts with number one in the first cell and try each one, whilst standard backtracking takes into consideration the 3 constraints of the sudoku and applies only those numbers and perhaps then doesn't start from number one in the first cell but may 2, 3. How do I choose to assign the most constrained varaible next?
I am implementing simple backtracking to solve a 9 x 9 grid, BT with backjumping to solve grids, BT with FC and BT with BJ and FC - I will be comparing the efficiency of using these different combinations. How will arc consistency, MAC etc improve this?
How do I generate a puzzle that is guarnateed to be logically solvable by a human only and not needing any guessing?
Thank you. |
|
| Back to top |
|
 |
| Adak
| | Joined: 27 Feb 2008 | | Posts: 87 | | : | |
Items |
|
| Posted: Sat Mar 29, 2008 3:38 pm Post subject: Re: few queries in solving sudoku |
|
|
| bhavina wrote: | Hey, just a few queries: if using just a simple backtracking algorithm to solve sudoku puzzles, how do I implement it so that each blank cell has all the possible values it can have and then a cell that has only one in its domian is assigned and then the cell with the smallest domain is assigned first etc? Would this entail dynamic variable ordering or static? Is that brute force just starts with number one in the first cell and try each one, whilst standard backtracking takes into consideration the 3 constraints of the sudoku and applies only those numbers and perhaps then doesn't start from number one in the first cell but may 2, 3. How do I choose to assign the most constrained varaible next?
I am implementing simple backtracking to solve a 9 x 9 grid, BT with backjumping to solve grids, BT with FC and BT with BJ and FC - I will be comparing the efficiency of using these different combinations. How will arc consistency, MAC etc improve this?
How do I generate a puzzle that is guarnateed to be logically solvable by a human only and not needing any guessing?
Thank you. |
My brute force guess function used to be a primitive "take the first cell and assign the first candidate it has to it, and go to the next cell and do the same. Test if it's legal. If so, continue to the third empty cell, and do the same," etc.
Candidate digits only are considered, not all digits, of course.
Newer brute force guess function has an array of 81 - 16 structs. Each struct has a row, column, number of possibles (num), and a few members in it. The board is quickly scanned once, and the info put into this array of structs (one dimension), which is then sorted according to the fewest number of possibles.
Also, there is an index to this locate[] array of structs, which is sorted so the next cell where a guess will be made, is always the cell with the fewest possibles. In my code this is static and never changes. The sort is done just once.
With each correct guess, the Locate[ply] array is incremented, ply++. With each guess found to be wrong, the Locate[] array is decremented, and the info in the structs is used to restore the Board[] array cell to it's last known good value. The locate struct has a .hi member, so when the highest possible candidate has been tried and wasn't right, then it knows to back up (decrement the ply), and increment the next to the last cell it changed, (if possible), and then start testing values on that last cell, starting with the lowest possible candidate.
Because of the index[], and since for some weird reason I chose to do it without using recursion, my code looks like Saturday's stew a bit, but it's OK once you get adjusted to the index stuff:
I have a board array, a separate PossAll array, and another array like board, but it only tells me what were the givens in the original puzzle - nothing else.
My brute force solver misses the boat a bit because it never propagates anything after a correct guess, blithely going on to the next guess w/o a care in the world of exploiting what it just discovered 
It's blindingly fast on smaller number of candidates, but it doesn't do much to quickly cut down the number of candidates when confronted with a puzzle like Gordon's Sudoku 17 #11, which has a lot of candidates left to be searched through, after my logic functions are done. (They would need to be able to find Swordfish, and can not do this, yet).
My first version of this used a 2 dimension possibles array, and I believe I might go back to that size array for this, eventually. Just for the speed. 
You might try loading a puzzle grid, and having your solver try to solve it, while it's "higher" logic and brute force guessing functions have their calls remarked out //. If your program can solve it with just basic logic functions, then it's certainly one that a human could solve, with some practice and skill. |
|
| 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 |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
