Sudoku Solver

[Aange10]

So I'm indulging on a project in which I solve Sudoku puzzles.

Here is what I know:

1) Every row must have 1-9 with no repetitions.
2) Every column must have 1-9 with no repetitions.
3) Every 'Box' must have 1-9 with no repetitions.


I understand how to check to see if one is correct, but how would I go about solving one? The only thing I could think of would be to randomly generate non repeating numbers for each row/column and run the tests untill a good combo comes up. But, that would take forever and is extremely inefficient.

So my question is:
How should I begin 'guessing' numbers?

[Zren]

Assuming you had a solvable grid.

All empty squares have the possibility of being 1-9.
Take the first square you're not sure of, and check each of the rules for all possibilities. It should eliminate some. Iterate over all squares with possibilities. When all but one possibility is left in one of the squares, there's your answer for it.

That should solve 'Easy' level sudoku boards.

Once you run through all the squares without eliminating a possibility that round, you will need to add more rules that build on the obvious ones and/or join the realm of recursion.

[Aange10]

Thanks for your response, Zren. This seems like it will be challenging.

[mirhagk]

Extremely so, unless you use brute force methods. Actually it could be an interesting introduction to Prolog, you simply write the rules and it solves it for you (using brute force of course). If your interested you should look into it.

[Raknarg]

I have a thought, idk if this is any use.

step 1. go through each empty element one by one and check to see if any squares are solvable.

step 2. if you've gone through the entire list once without solving anything, then look through the list for a block with the least possible answers (starting from 2, obviously). Then recursively create two new paths, one where you used one answer, the other where you used a different answer.

step 3 repeat steps one and two until an answer is found or until no more moves are possible.

Thats what I would try, anyways. There's probably better methods

[evildaddy911]

When i do sudokus i usually start off looking through 1-9 for each (big) box, then do rows/colomns. Then i go back over it again untill i cant get anymore #s. I then go (small) square by square looking for one where only 1 # can fit. I repeat untill the puzzle is complete

[mirhagk]

@evildaddy, try a non-trivial Sudoku, that strategy won't work.

[Raknarg]

Actually, I just finished it yesterday. I haven't tried anything really complex yet, but it seems to be able to solve puzzles effeciently. You can take a look here:

http://compsci.ca/v3/viewtopic.php?p=257959#257959

It's basically what evildaddy suggested, but it includes recursion after there are no single answers to check each number path to see which one will work.

[mirhagk]

I'd suggest getting reading an online article that explains tips to solve soduku. There are usually quite a few tricks that can severely reduce the amount of recursion you have to do.

[Ultrahex]

I actually wrote a Sudoku Generator + Solver in Grade 11? CS (Java).

Some of the interesting things that I still remember figuring out are:
- By permuting the rows in each block (e.g. rows 1-3, columns 1-3) in any order, including interwoven; you can produce all sudoku puzzles.
- All Sudoku puzzles do NOT have a unique solution depending on how many elements you 'hide' from the user (and in particular which ones)
- A combination of algorithms will produce the fastest solvers as some techniques are extremely slow while others are extremely fast (in practice).