|
View previous topic :: View next topic |
Author |
Message |
| Seaplusplus
| Joined: 23 Mar 2008 | Posts: 12 | : | | Items |
|
Posted: Sun Mar 23, 2008 7:58 pm Post subject: Making a solver - a few questions! |
|
|
Hello, Sorry if this information is already about (it probably is) but I havn't been able to find out certain things.
Basically, I am trying to make a sudoku solver which can solve any sudoku. I know there are two main methods. Logic and brute force. If i understand correctly, if the sudoku has a unique solution, then only logic is required. Is this right? (99% of the time)
If so, considering actually coding a program. How many bits of 'logic' do you have to implement for it to solve any sudoku with a unique solution. I have been seeing lots and lots of strange terms like 'XYZ pair' 'X wing' 'Hidden quad' 'BUG' FISH' etc. Are these simply techniques used to make us (humans) solve the puzzle more quickly, or are these required logics for which I must account for in my program.
Is a suitable approach to solve as much as I can with basic logic (logic that can solve easy/med puzzles) and then use brute force for the remainder?
So far i have coded the following logics:
1. only 1 type of number on each row/column.
2. only 1 type of number in each 3x3 block.
3. After checking the list of possible numbers for each block along a row/column. If a number only appears once, it must go there.
4. (trying this) if for a 3x3 block there is only 1 place a number can go, place it there.
note : the first 3 can solve easy/med puzzles fine it seems
Many Thanks,
Tim |
|
Back to top |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Sun Mar 23, 2008 9:57 pm Post subject: |
|
|
Welcome Tim,
Indeed, there are mainly two ways to solve a sudoku, by logic or by brute force. For the brute force part i can be short, please check the Sticky thread about Dancing Links.
What the logic way concerns, I recommend you the sudoku website from Andrew C Stuart, where you can lookup many definitions for most of the known strategies to solve sudokus. If a sudoku has only one solution, than it must be possible to solve it by logic alone. However, you must be aware that the known logics do not cover solving 100% of all sudokus. But don't worry, even the hardest ones published in magazines, newspapers, puzzle-magazines, ... can be solved with just a few off the known techniques.
These are those few techniques:
Naked Single
Hidden Single
Pointing Pair
Box Line Reduction
Naked Subset
Hidden Subset
Techniques beyond these requires pencilling in. Even naked and hidden subsets are balancing on the edge of the need for pencilmarks.
You can mix logic with brute force as you suggested, it all depends on how hard you want to level up your generated sudokus and either want to discard those that can not be solved by the implemented logic of your program, or not.
You can always look at the source code from my Generator/tester. It is written in Visual Basic 6, which is an easy language, to read and understand. The code is in the file called Main.frm which can be opened by any text-editor. It uses brute force to check uniqueness, and the generator includes some algorithm to search for naked singles, hidden singles, box/line reduction, pointing pair and naked/hidden subsets before invoking brute force.
Succes _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
Back to top |
|
|
| Adak
| Joined: 27 Feb 2008 | Posts: 87 | : | | Items |
|
Posted: Mon Mar 24, 2008 12:18 am Post subject: Re: Making a solver - a few questions! |
|
|
Yes, logic and then brute force, is a great combo to use. I would lower that 99% figure however, to 88% of puzzles being solved by "simple" logic, alone. I wouldn't say that you have all the simple logic you need for your program, just yet.
As someone who is also a relative beginner, I'm quite convinced that life is simply too short to try and code up all the various "hard" ways of solving a sudoku puzzle.
I'm not quite certain what you program already does, but I'd recommend it include:
Locked Candidates type 1
Locked Candidates type 2
Inside and Outside Rule of Pairs (and possibly triples)
X Wing
Swordfish
The last two I'm just learning to do via a graphing technique. More info at Sudopedia, subject: locked sets
It's satisfying seeing your program not only solve the puzzle, but be able to tell you HOW it solved the puzzle. Not in brute force methodology: "I guessed at 5,000 combinations of digits in 22 cells before arriving at the correct answer", but something a human solver could use: "found locked candidate type 1 at row 6, column 3, which eliminated the 3 at row 6 column 5 and ...etc".
What language are you programming in? (If you answer "English", be ready to duck. ) |
|
Back to top |
|
|
| Seaplusplus
| Joined: 23 Mar 2008 | Posts: 12 | : | | Items |
|
Posted: Mon Mar 24, 2008 2:24 am Post subject: |
|
|
Wow, thanks for the information guys. I appreciate it.
I have written some code in visual c++. I think I'm going to start again though, as my code got a bit out of hand and fairly messy. I am going to try and simplify my methods (i was using linked lists, i might try using bitsets instead for example). This should then make it easier for me to implement the logic .
That site you linked me seems very useful. So I think I will go with just the main logic pieces and then go brute force! |
|
Back to top |
|
|
| hobiwan
| Joined: 11 Feb 2008 | Posts: 83 | : | | Items |
|
Posted: Mon Mar 24, 2008 12:51 pm Post subject: |
|
|
If you are going to rewrite your code, try to use a data structure that allows you to treat rows, columns and blocks using the same code (for example a simple array with 81 entries, plus predefined arrays for the indexes of every house). You can than code a very simple function to say find naked pairs in a house and use that function for every possible house by just passing your function a different index-array. |
|
Back to top |
|
|
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Mon Mar 24, 2008 3:51 pm Post subject: |
|
|
[Withdrawn: I mistakenly thought bitset was the same thing as I'd been calling bitmap. So my comments were misdirected.]
Last edited by daj95376 on Thu Mar 27, 2008 12:36 am; edited 1 time in total |
|
Back to top |
|
|
| dmhayden
| Joined: 01 Aug 2007 | Posts: 16 | : | Location: Central New Jersey | Items |
|
Posted: Mon Mar 24, 2008 10:07 pm Post subject: |
|
|
I agree with Hobiwan, although I did it slightly differently. My solver has a method called forEachGroup(). It takes as an argument a pointer to a function that looks like this:
Code: |
void *callback(Square *squares[]);
|
In other words, the callback function takes an array of pointers to squares. forEachGroup will call callback() 27 times - each time the elements of the array point to a different row, column, or box. Once you have this, you can write many algorithms as callback functions.
I'm not sure what daj95376 is referring to when he/she talks about "bitset support arrays". My solver has no such thing.
Finally, if you're rewriting, try to separate the solving logic from the user interface. This will come in handy when you want to pump a file full of puzzles through your solver for testing or performance tweaking.
Good luck!
Dave |
|
Back to top |
|
|
| hobiwan
| Joined: 11 Feb 2008 | Posts: 83 | : | | Items |
|
Posted: Mon Mar 24, 2008 11:11 pm Post subject: |
|
|
I don't want to speak against bitmaps, they are incredibly useful. I just think, that they have drawbacks too (for example iterating over them again and again is rather slow, they can hold only one value per cell...).
In fact I use a bitmap backed by an array to get the best of both worlds: Bitmap operations are most powerful when you are working with sets (eg: give me all cells, that can see all fins in a fish - with bitmaps this boils down to a few ANDs, without you need loops in loops...). I do all the necessary operations with bitmaps, then when I have to iterate, the array is filled and used.
As for predefined sets - some examples: One bitmap for every cell, that has all buddies set; one bitmap for every value that has every possible candidate location set; one set for every value, that has all cells set, where that value has already been applied...
dmhayden wrote: | My solver has a method called forEachGroup(). It takes as an argument a pointer to a function that looks like this: |
I code in Java, so no pointers to functions (references to instances of classes that implement interfaces, but that can get a bit tiresome...). |
|
Back to top |
|
|
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Tue Mar 25, 2008 2:11 am Post subject: |
|
|
[Withdrawn: Earlier comment edited instead.]
Last edited by daj95376 on Thu Mar 27, 2008 12:38 am; edited 1 time in total |
|
Back to top |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Tue Mar 25, 2008 3:21 pm Post subject: |
|
|
hobiwan wrote: | I don't want to speak against bitmaps, they are incredibly useful. I just think, that they have drawbacks too (for example iterating over them again and again is rather slow, they can hold only one value per cell...).
|
like daj said there is probably a disconnect on bitmap between C and C++
I'll use C bitmask to differentiate
the main reason for using a C bitmasks is so single instructions can operate on multiple values
re sudoku
represent each value from 1..9 as a bit (1<<0)..(1<<8)
then each cell in the grid requires 9 bits, or a [unsigned] short in C
this allows the grid be represented as an array of 81 [unsigned] shorts
this array is exactly the pencilmark grid where a solved cell (or clue cell) has only one bit set
the precomputed bit arrays daj mention would be something like these (for 9 bits)
count[x] the number of bits set in x
next[x] the next bit in x
look at the C code daj linked to above to see these in action
in that code the basic sudoku constraints are also implemented as bitmasks
you will be hard-pressed to get similar performance without bitmasks |
|
Back to top |
|
|
| hobiwan
| Joined: 11 Feb 2008 | Posts: 83 | : | | Items |
|
Posted: Tue Mar 25, 2008 5:34 pm Post subject: |
|
|
gsf wrote: | like daj said there is probably a disconnect on bitmap between C and C++
I'll use C bitmask to differentiate |
Ok, now I am getting really confused. From my C days (which have been over for some time now, so please forgive me if I am not up to date) I know a bitfield, but no bitmap or bitmask. From your description of a bitmask I can't see the difference to a C++ (or Java) bitset, except that it isn't a predefined class from a library, but code written by yourself.
Semantics aside, what I meant with bitmap is exactly what you described (I even use your short-bitmask for storing candidates in a cell, including your count[x] array). But I find a second bitmap even more useful when coding solution techniques: A class with two 64bit integers using one bit for every cell in the grid (and yes, three 32bit integer would have wasted less memory and even been considerably faster, at least in a 32bit JRE, but I think, that will change soon). It was that type of bitmap I meant, when I said, that it can store only one value for a cell (I use predefined arrays like count[x] for that bitmap too, but only 8bit wide, which I have to map to the bytes of my integers).
gsf wrote: | you will be hard-pressed to get similar performance without bitmasks |
I totally agree with you of course.
gsf wrote: | this array is exactly the pencilmark grid where a solved cell (or clue cell) has only one bit set |
How do you differentiate between a naked single and a solved cell? I use a second short for that (you could of course store that info in the bitmap either, but I was to lazy to code that). |
|
Back to top |
|
|
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Tue Mar 25, 2008 8:46 pm Post subject: |
|
|
[Withdrawn: Not really worth sharing.]
Last edited by daj95376 on Thu Mar 27, 2008 12:40 am; edited 1 time in total |
|
Back to top |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Tue Mar 25, 2008 10:22 pm Post subject: |
|
|
hobiwan wrote: |
gsf wrote: | this array is exactly the pencilmark grid where a solved cell (or clue cell) has only one bit set |
How do you differentiate between a naked single and a solved cell? I use a second short for that (you could of course store that info in the bitmap either, but I was to lazy to code that). |
each cell is intersected by 3 9 bit masks corresponding to the row/col/box for the celll
(this is the MASK() macro in the code daj cited)
in the initial grid clue cells have 1 bit set and non-clue cells have all bits set
a sweep of the MASK() anded with each cell across the grid exposes naked singles
(by producing cells that go from >1 bit to exactly 1 bit)
in a backtrack search wrong guesses will yield cells with 0 bits on when anded with MASK() |
|
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
|