Sign in to follow this  
Manacube

Sudoku Solver

Recommended Posts

Hey all, im working on a program that can solve a sudoku puzzle and i needed some advice for the solving part. im using vc++ 6. im using a 2-D array to store the values that are given for the puzzle, and to solve it im thinking about using a call to a function that will find all the possible numbers for each element. From there im going to test if there is only element in each (row/column/square) that can have a particular possible value, so i can know that that is the only place that the number can go. Example: if there is only one spot in the 3rd row that can have the value 7, then i know it has to go there. My question comes into mind about how to store all the possible values for each element without having to make massive data structures for each element. Do you all have any suggestions? Im looking for something like Java's ArrayList function or something. If you have a better way of solving it, that would be cool too. Thanks in advance

Share this post


Link to post
Share on other sites
Well I guess there are a lot of ways to do this. The first and most obvious/naive approch might be to use some kind of structre like

struct GridCase
{
int number;
bool possibilities[10]; // or pack into a int...
};

GridCase sudokuGrid[9][9];


And your algos could be performing on this. I think you're not looking for something that has to solve one bazillion grid a second do you ? ^^

I'm just intersted in how you're going to do this, since a while ago I too happened to think about how a computer could beat a sudoku grid. At first I thought it would be easy, that I just had to list every potential candidate in every compartment, and then remove every number that could not stand there. But as I played more, I realized that there was lots of ways to eliminate a number and get to the solution. And with top difficulty level grids, using the basic approach will not even yield a single number, I mean that after a first step processing the grid as you described, there will not be any compartment where only one number is left. And all further iteration will lead you in an infinite loop.

Well... I was just thinkin aloud and not tellin you what you have to do. Just wanted to point out the fact that it might not be as simple as it first looks like.

There are alot of resources about this topic. I gave a try googling it and those I found ended being pretty much similar regarding the techniques they described. I just picked a random one There are some basic techniques that look simple to implement and others that look quite trickier... I want to think about that again now :)

Well done manacube, I feel like you've revived my interest for sudoku :)

Share this post


Link to post
Share on other sites
Like the previous poster suggested, I would first determine the possible values for each empty space based solely on the numbers in its 3x3 square. I would then make a second pass that further narrows the search space by eliminating more numbers based solely on the row of the space, and a third pass eliminating more numbers based on the column. You will then have an array of possible numbers (and/or impossible numbers) for each empty space.

After that you may have to use some sort of brute force... I think that's basically what we do when we solve them. Some recursive, backtracking algorithm perhaps.

You could add some simple common-sense enhancements, though. When you are trying a new number, don't recalculate the search space for the entire 9x9 grid... just the local 3x3 grid and those 3x3 grids which are horizontal or vertical to the local one (but only if the relevant row or column has empty spaces).

Share this post


Link to post
Share on other sites
Brute force is simple to implement and executes very fast.

def Solve(board):
if board is invalid:
return None
espace = first empty space in board
for i in range(1,10):
solution = Solve(board with espace set to i)
if solution != None:
return solution
return None

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Brute force is simple to implement and executes very fast.

def Solve(board):
if board is invalid:
return None
espace = first empty space in board
for i in range(1,10):
solution = Solve(board with espace set to i)
if solution != None:
return solution
return None

Well, this brute force algorithm can be optimized to "return None", so I guess it's very fast (but may not give you all the possible answers) [grin]

Anyway, the base idea is the correct one: brute force solver is the way to go.

Regards,

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I don't think so

The algorithm seems quick and easy. But only because you hide all the effort in the "is valid" part.

You will end up with the same arrays of bools.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
I don't think so

The algorithm seems quick and easy. But only because you hide all the effort in the "is valid" part.

You will end up with the same arrays of bools.


No, it's quick and easy because it is really quick and easy. And there's not "is valid" part - a sudoku that is not invalid is, by definition, valid (and testing the validity of a sudoku is rather simple).

Did I miss something? I find your post rather obscure (as I don't fully understand its context)

Regards,

Share this post


Link to post
Share on other sites
Quote:
Original post by Emmanuel Deloget
Well, this brute force algorithm can be optimized to "return None", so I guess it's very fast (but may not give you all the possible answers) [grin]

Er, yes. Stick a "if board is complete: return board" right after the validity check.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
I don't think so

The algorithm seems quick and easy. But only because you hide all the effort in the "is valid" part.

You will end up with the same arrays of bools.

"is valid" is very simple; you just check for non-unique integers in each row, column, and square. I don't know what arrays of bools you're referring to.

Share this post


Link to post
Share on other sites
I solved a Sudoku puzzle before, but I did that using Prolog. A Sudoku board can be expressed as a constraint satisfaction problem quite easily, so just plugging in the values allows it to be solved real quick =)

Of course, I'd probably rather chew my own arm off than have to use Prolog again =)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
see the arstechnica forum, there's a complete thread -including solutions for a solver.

Share this post


Link to post
Share on other sites
The latest issue of Scientific American has an article on Sudoku's and different strategies to solve them and create them. A tiny excerpt of the article is available on the site, scroll down to Mathematics to get to it.

Share this post


Link to post
Share on other sites
Sudoku is a 9x9 grid of cells.

81 cells.

If 33% of them are filled, that leaves 54 cells.

10 possibilities per cell.

10^54 possible solutions.

So a Sudoku program that only checked for validity after the entire solution was filled is not feasible.

The "brute force" algorithm above isn't actually brute force. It uses early pruning so it does't have to describe all 10^54 solutions.

I can't figure out off the top of my head how good that pruning will end up being in the worst cases.

However, solving a Sudoku is less interesting than finding Sudoku's that can be solved by a limited set of Sudoku rules. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this