Jump to content
  • Advertisement
Sign in to follow this  
Manacube

Sudoku Solver

This topic is 4436 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!