Making a solver - a few questions!

Seaplusplus

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

Lunatic · 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
~~~<><~~~<><~~~<><~~~<><~~~

Adak

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:

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. Very Happy

)

Seaplusplus · 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 Smile

.

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!

hobiwan · 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.

daj95376 · 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.] Sad

dmhayden · 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:

hobiwan · 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...

daj95376 · Posted: Tue Mar 25, 2008 2:11 am Post subject:

[Withdrawn: Earlier comment edited instead.]

gsf · Posted: Tue Mar 25, 2008 3:21 pm Post subject:

hobiwan · Posted: Tue Mar 25, 2008 5:34 pm Post subject:

daj95376 · Posted: Tue Mar 25, 2008 8:46 pm Post subject:

[Withdrawn: Not really worth sharing.]

gsf · Posted: Tue Mar 25, 2008 10:22 pm Post subject: