Programming Design Help - How to Structure a Sudoku Solver program?

Question

Hi, I'm trying to create a sudoku solver program in Java (maybe Python). I'm just wondering how I should go about structuring this...

Do I create a class and make each box a object of that class (9x9=81 objects)? If yes, how do I control all the objects - in other words, how do I make them all call a certain method in the class?

Do I just create functions to calculate and just control all the numbers in there with something like an multi-D array?

And actually, even if I could just create multiple functions, how would I control all the objects if I were to make each box an object?

Thanks.

Answer 1

Don't over-engineer it. It's a 2-D array or maybe a Board class that represents a 2-D array at best. Have functions that calculate a given row/column and functions that let you access each square. Additional methods can be used validate that each sub-3x3 and row/column don't violate the required constraints.

Answer 2

Maybe a design that had a box per square, and another class to represent the puzzle itself that would have a collection of boxes, contain all the rules for box interactions, and control the overall game would be a good design.

Answer 3

Well, I would use one class for the sudoku itself, with a 9 x 9 array and all the functionality to add numbers and detect errors in the pattern.

Another class will be used to solve the puzzle.

Answer 4

Do you need to do it in Python or Java? I do a lot of programming in Python, but this can be done much more concisely with integer program using a language like AMPL or GLPK, which I find more elegant (and generally more efficient) for problems like this.

Here it is in AMPL, although I haven't verified how this works: http://taha.ineg.uark.edu/Sudoku.txt

Answer 5

The simplest way to do it is to represent the board by a 2D 9x9 array. You'll want to have references to each row, column and 3x3 box as a separate object, so storing each cell in a String makes more sense (in Java) than using a primitive. With a String you can keep references to the same object in multiple containers.

Answer 6

If you're stuck and are interested in a walkthrough of a solution, Peter Norvig wrote an article on a Sudoku solver implemented in Python.

Answer 7

First, it looks like there are two kinds of cells.

• Known calls; those with a fixed value, no choices.

• Unknown cells; those with a set of candidate values that reduces down to a single final value.

Second, there are several groups of cells.

• Horizontal rows and Vertical columns which must have one cell of each value. That constraint is used to remove values from various cells in the row or column.

• 3x3 blocks which must have one cell of each value. That constraint is used to remove values from various cells in the block.

Finally, there's the overall grid. This has several complementary views.

• It's 81 cells.

• The cells are also collected into a 3x3 grid of 3x3 blocks.

• The cells are also collected into 9 columns.

• The cells are also collected into 9 rows.

And you have a solver strategy object.

1. Each Unknown cell it set to having set( range(1,10) ) as the candidate values.

2. For each row, column and 3x3 block (27 different collections):

   a. For each cell:

   • If it has definite value (Known cells and Unknown cells implement this differently): remove that value from all other cells in this grouping.

The above must be iterated until no changes are found.

At this point, you either have it solved (all cells report a definite value), or, you have some cells with multiple values. Now you have to engage in a sophisticated back-tracking solver to find a combination of the remaining values that "works".

Answer 8

A class containing a 1d array of 81 ints (0 is empty) is sufficient for the rule class. The rule class enforces the rules (no duplicate numbers in each row, column or 3x3 square). It also has an array of 81 bools so it knows which cells are fixed and which need to be solved. The public interface to this class has all the methods you need to manipulate the board:

int getCell(int x, int y);
bool setCell(int x, int y, int value);
bool clearCell(int x, int y);
int[] getRow(int x);
int[] getCol(int y);
int[] getSubBox(int x, int y);
void resetPuzzle();
void loadPuzzle(InputStream stream);

Then your solver uses the public interface to this class to solve the puzzle. The class structure of the solver I presume is the purpose of writing the 5 millionth Sudoku solver. If you are looking for hints, I'll edit this post later.

Answer 9

just for fun, here is what is supposed to be the shortest program, in python, that can solve a sudoku grid:

def r(a):i=a.find('0') if i<0:print a [m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)]or r(a[:i]+m+a[i+1:])for m in`14**7*9`]r(raw_input())

hmm ok it's quite cryptic and I don't think it matchs your question so I apologize for this noise :)

Anyway you'll find some explanation of these 173 characters here (sorry it's in french)