Easily programmable solving techniques

Everything about Sudoku that doesn't fit in one of the other sections

Easily programmable solving techniques

Postby ThemePark » Tue Feb 24, 2009 9:11 pm

I'm not really sure whether to put this here, in the Advanced Techniques forum, or the Programming forum, but oh well.

I am attempting to program a simple solver in Java. And I would like to know, besides obviously removing all possible occurences of a set number in its row, column and box, and marking a number as set if it is the only option in its field, what are some of the easier sudoku solving techniques to implement in programming?

And also, are there a number of techniques I can include in my solver and be sure to solve most sudokus, or would I just have to implement basically all known techniques for that?
ThemePark
 
Posts: 13
Joined: 27 September 2008

Re: Easily programmable solving techniques

Postby tarek » Tue Feb 24, 2009 9:56 pm

ThemePark wrote:besides obviously removing all possible occurences of a set number in its row, column and box, and marking a number as set if it is the only option in its field, what are some of the easier sudoku solving techniques to implement in programming?

For somebody who deosn't use the terms hidden or naked singles ... I would recommend improving your sudoku terminology before asking any question.

How do you do that ?

Read around:idea:

[Edit: Technology --- > Terminology]
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ab » Thu Feb 26, 2009 1:24 am

as Tarek said the first thing you need is hidden and naked singles. You will then have a trivial solver. You can beef it up a bit by adding locked candidates of which there are two varieties. Next up add hidden and naked pairs. Once you've worked out how to do them hidden and naked triples and quads shouldn't be too hard to add. Also it's quite easy to convert your code for hidden and naked pairs to work for x-wings, and for hidden and naked triples to work for swordfih and hidden and naked quads to work for jellyfish. Once you've done all that you'll have a reasonable solver. People make much more advanced solvers though:!:
ab
 
Posts: 451
Joined: 06 September 2005

Postby Smythe Dakota » Thu Feb 26, 2009 11:56 am

If you're creating a solver program which can (eventually) solve any Sudoku (which has a unique solution), you will eventually have to resort to trial and error. Because of this, you might want to omit some of the more advanced techniques. Just invoke naked and hidden singles, pairs, triples, quads, etc, and maybe locked candidates. Then let T&E take over!

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006


Return to General