Sorry your browser is not supported!

Fun fact: Sudoku was made in America, but popularized in Japan...

My solver can solve any Sudoku puzzle with only 1 solution. While this pretty much covers any puzzle in newspapers and other articles, there are very challenging ones where guessing is pretty much required.
Tools at your disposal:
-dim slot(9,9) as string - Stores all data of what each slot could and couldn't be. Each slot can also be accessed by a single integer 0-80 (81 slots in total).
-logical_solve() - Solves the current puzzle as far as it can without guessing.
-check_complete() - Checks if the current puzzle is complete. If it is, it returns a -2. If it is invalid (ex: two 9's in the same column), it returns -1. If it is incomplete, it returns the first slot in integer form (0-80 as discussed before) which still has possible values.

Goal:
I need a good way for the program to solve a partially complete puzzle which has all remaining blank slots with multiple possibilities. I've considered a brute force method, but have yet to come up with a good one. I've tried writing a "guess one, logical solve the rest" but it is lengthy and incomplete since so many things could go wrong.
Critical situations to consider:
-Guess a slot, logical solve, have to guess yet AGAIN (repeat this a few times), ends in dead end.
-Blank sudoku puzzle

My personal belief is that the best method would be a brute force method because it should be quicker to write, and fairly quick for a computer despite inefficiencies. Ideas?

edit: check_complete() wasn't correct. If samples of codes are needed, I can provide them on whatever. Pseudo-code is just fine as an answer. I can't seem to find a good way to crack this ><

check out my solver,i did it as part of a gui program i was writing to test out the button and window functions.I have a stripped down version of just the solver and generator that that spits out puzzles and solutions rated easy to hard ready for a few books i wrote for friends and family.If you want the code to that let me know,this is a link to the GUI projecthttp://forum.thegamecreators.com/?m=forum_view&t=154675&b=8

This can only solve puzzles with one solution. For instance, if you tried to solve a blank puzzle, it'll just tell you that every square has every possibility. This is essentially what my logical_solve() does. I need a good guessing algorithm, whether it be brute force or systematic approach, to be able to guess just 1 of the many solutions to a sudoku puzzle, even if the puzzle is blank. There are some "extreme" puzzles I've found on the internet that require educated guesses rather than shear logic.

Novaguy,the one in the GUI example i posted a link to is only solving logical puzzles with one solution,but the one thats part of my generator/book publisher uses a recursive routine to check for multiple solutions,thats one of the criteria it uses to rate the puzzles,and why it can take less than 10 seconds to find and check 10 "easy" puzzles but may take 10 hours to find and check 10 "diabolical" puzzles.If you want the code to the any of the above let me know,i'm not at home right now so it may take a few days for me to post it.
The GUI version is only ment as a helper to solve some of the harder puzzles as you can manally try different solutions then undo the results and try a differerent way,which is basically what my later solver routine tries to do.

If guess work is involved, then it's not a true Sudoku, and so really if there are multiple solutions, you need to store and keep track of each tried solution.

I would use a buffer of boards, like do all the logical moves possible, then for each option, copy the board and perform the move. I'd probably store the state of each board in the buffer too, like whether it has been solved or if it ends up with no logical moves. So you'd step through the board, get a buffer for each logical move, then try and solve those - keeping track of the ones that have been checked, and branching more and more for each possible option. A lot like Chess AI I guess. Repeat until you have a valid solution, one that ends in a complete board.

The minute you allow guessing, the problem gets a whole lot more difficult. I'm finishing up a Sudoku game, and it used to make those puzzles that required guesswork, but that's not really the game I want to make, frustrating, slow, and only really of interest to extreme Sudoku fans. So my game only uses single solution puzzles - I think it's more like a speed-Sudoku, as theres a really handy hint system, automatic notes, valid move highlighting etc etc - I can do a difficult puzzle in about 3 minutes with the hints on.

Personally, I would advise that the minute you introduce guess work into your puzzle, is the minute your puzzle ceases to be a Sudoku. Maybe it's best to stick to pure Sudoku's, with their easy solutions, less frustrating gameplay, faster and steadier games. If I do a Sudoku, and I have to make a guess, then the puzzle looses something, it becomes less of a puzzle and less elegant I think.

Soduko generator and book creator programs,the file names are hard coded in this version to the folder thats included in the download.
Run the generator first and wait until the counter reaches 50 for each puzzle type.Then run the book creator,all the images will be saved out ready for printing.The later version on my PC back home has file selector at the begining,i´ll post it later if you want.It may take overnight to get all 50 of the diabolical puzzles,but they are very hard,but all solveable by logic only methods.

I think for building pure sudoku solver you first need to have flawless understanding even for hardest logics used in it for solving.I`m pretty good with this puzzle, i play when there is free time.Once my friend which is even better than me watch me while i stuck with one sudoku.I was about to give up, when he find the solution to it, even when he explain me his logic twice i didn`t understand him, it was too complicated.But he is real sudoku master.Logical ninja I`m pretty sure that every sudoku can be solved without guessing.

Apart from being false if taken literally, how can you improve on that? No "algorithm" will fill in the missing information for you. If multiple solutions are possible then any guess that fits should suffice - unless you expect your "algorithm" to know how the setter thinks (or is programmed).

[Aside: it is not true without qualification that "every square has every possibility". For each square taken in isolation, then yes - but valid solutions must satisfy the Sudoku rules which restricts the number of solutions enormously. If I were programming this then I'd probably use a "branch and prune" strategy to find the answer - pure brute force might be fast enough with today's machines (I rather doubt it - but haven't done the sums ).]

I found it best to work backwards, start with a complete board generated through brute force, then recurse through the whole thing looking for single moves, and deleting that cell. If there is only 1 valid move then the cell can be cleared, doesn't take too long to do that, as even solving the board several times over is quite quick.

http://www.eddaardvark.co.uk/sudokusolver.html

@luskos
There are some logic routines that I haven't included in logical_solve() because they are far too hard for me to describe to a computer efficiently. In these cases, I think it'd be best to just have a brute force method. It'd take much less time to program, and not much more time to solve. In the link above, see the "pairs" section. I think programming that would take too long unless you have a real fast way.

@Van B
See the link above. The last puzzle he walks through has 32 solutions. I agree that guesswork takes away from the puzzle, but I want to make an infallible solution generator that will even solve a blank puzzle.

@Green Gandalf
Sounds like a GREAT counting problem I will present to my math professor . How many total maps can you make, both valid and invalid, and how many of those maps are valid. From there, you can do all sorts of fun stuff. Also, I have read other websites where brute force methods are used, and they seemed to work. One was clocked at <500ms.

The brute force method I'd like to implement is just so I don't have to describe every logical situation to the computer. I did the most simple and common ones found in sudoku, but some are just too long to describe. A brute force method would save me time programming and fill in all of the logic techniques I missed.

Say you had 3 blank slots left (in reality, hard ones would have a lot more left after my logical_solve() function. For now, lets pretend 3 is a large number). Slot 1 has 3 possibilities, slot 2 has 5 possibilities, and slot 3 as 2 possibilities. How do I get it to guess each situation? There's always this:

Slot 1 2 3
Choice 1 1 1
1 1 2
1 2 1
1 2 2
ect... counting up, doing check_complete() after every one until a -2 is returned.

This shouldn't be too hard, but I was hoping someone would come up with a cool idea to use logical_solve() in conjunction with this brute force method to make it go faster, and perhaps eat less memory. Obviously memory isn't going to be a real issue, but I like my programs to have certain slim fast diets.

edit:
@paul5147
These programs are AMAZING. Can you send me the code for these 2, or is it part of that GUI package from earlier? I didn't remember seeing it. I'd like to see the logic you used for the diabolical ones.

Novaguy,The logics fairly simple to follow,the way my solver runs if it only takes 1 pass through the solver its an easy puzzle,2 medium,3 hard,4 very hard and anything over 4 is a dibolical puzzle.
The easiest way i've found to make the solver is with 2 arrays.
given(9,9) which is the numbers you start off with and any you find later with the solver.
possible(9,9,9) think of the grid as a cube made of nine layers,each layer represents a possible number,if that numbers possible in that position then that element is set to a 1 otherwise it becomes a zero.
So possible(1,1,7)=1 means its possible to have a seven at 1,1-top left.
You loop through the given(1-9,1-9) array with all the numbers that make up the start of the puzzle,for every number you follow the basic sudoku rules.
If given(3,3)=9 then all the top left square possible(1-3,1-3,9) will become 0 and the same for the row and column possible(1-9,3,9) and possible(3,1-9,9)
To do a basic search you then only have to loop through possible(1-9,1-9,1-9) counting how many 1's make up each position and if the total only comes to 1 then that position can only have one possible number so you add it to given and then update the possible array in the same way as before when adding the original numbers.
There are quite few more logical steps that can remove possible numbers but the basic search will allways be the same.
Say a block only has 2 or 3 posible places to put a 1 and there all in a line,then you dont know the position but you no there cant be another 1 on that line in the adjacent blocks so the possibles array can be updated to show that as well.Its all just a matter of nested for/next loops and searching/manipulating the possibles array before doing another search.
Hope this points you in the right direction,if not let me know and i'll post you the code as soon as i get back home to my main PC.
The hard part of whole thing is not the solver,its actualy creating the full answer puzzle to begin with.Once you have that you then have to remove numbers in a mirror like or random pattern depending on the style your going for and then run it through the solver to rate the outcome.
If you have run the other 2 programs to completion you should by now have a set of folders full of image files ready for printing out in a book format(ring bound) including page numbers and titles.
So forgive me if im a little cagey as to the exact way this is done but you can see the financial application of this by now,brand new 250 puzzle sudoku book on demand every day with hardly any work or overheads.It will never be the next Dan Brown book but you have to start somewhere.