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

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 :)

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).

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

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.

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.

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.