Java and Sudoku

[Avellon]

So I've been working on a problem in Java where I create a class Sudoku, which I've made using a 2 dimensional array.

For anyone who might not know, a sudoku is a 9*9 square of cells, each cell contains a number.
The rules of Sudoku are very simple:

* Every column must contain the numbers 1-9 inclusive (this automatically means it must only contain each number once)
* Every row must contain the numbers 1-9 inclusive (this automatically means it must only contain each number once)
* Every 3*3 major sub-square must contain the numbers 1-9 inclusive (this automatically means it must only contain each number once)

So it might look like this,

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

Of course this isnt a valid solution, as the 3*3 subgrids don't have 1-9.

My problem comes in that I'm trying to create the sudoku, and then give a message if its a valid solution or not. I'm kind of new to Java, and was wondering what would be the best means to create an algorithm to search thrrough the rows and columns and subgrids to see if 1-9 is there, and if not to return back false as well as where in the sudoku the solution first wasn't satisfied.

Would a linear or binary search work here? Or how would you implement a solution?

This is sort of the framework I'm working on.

import java.io.*;
import java.util.*;
public class Sudoku {
private int[ ][ ] puzzle;
private String message;
public Sudoku ( String fileName ) throws FileNotFoundException {
. . .
}
private boolean isRowValid(int row) {
. . .
}
private boolean isColumnValid(int col) {
. . .
}
private boolean isSubSquareValid(int row, int col) {
. . .
}
public boolean isASolution() {
. . .
}
public String toString() {
. . .
}
}

[Vorph]

Do you have to actually solve a puzzle or just determine if a given 9x9 grid is valid under the rules of sudoku?

If you're just checking for valid grids, a linear search is the simplest way (binary is for sorted lists). Not the most efficient thing in the world, but for evaluating a single 9 by 9 grid it doesn't really matter. Looking for duplicates is probably a little more efficient, but at 6AM I make no promises about my ability to calculate big O.

Solving a puzzle is a lot more complicated and you should read up on how a backtracking search algorithm works.

[Zuuljin]

Seems fine to me. Just have it search each row/column linearly, and a mini search for each 3x3 square.

I actually wrote a sudoku app in java for fun awhile ago, but I actually built each puzzle from the start, and just saved the answer to compare too at the end, so I dont have it check the whole board.

[Zippygoose]

Like Vorph said, do a linear search since binary is for sorted lists. The groups you are validating are so small, however, that you could use any method of searching (however inefficient) and not really see a difference in performance.

If this is for a class though, you'll want to use best practices of course

[Avellon]

Thanks for the help all.

Yea, I only need to validate the rows/columns/squares under the sudoku rules. I'm not yet at a point to solve it.

I know I would be able to search to see if 1-9 were in particular row/column/grid, would it also work to see if one of the cells was blank, or if there were more than one of the same number, like 3 in 2 different cells in a column?

[Kallian]

You could scan a row/col for 1-9, adding up the total number of each number like so:

int [] check = new int[9];

as you scan a row, keep track of totals like:
check[n - 1]++;

where n is the number you just read in.

check[0] would contain the total number of 1s.
check[1] would contain the total number of 2s.
etc.

if each element in the array is 1, then you're good, else, you're not.

[Zippygoose]

It's threads like this that make me want to start periodic "problem threads". They wouldn't be someone's school assignment (although it's fun to help with those too) but rather just a generic problem to be solved. People could post their solutions and we could decide on the best/fastest/most efficient solution. I suppose that may be beyond the scope of this board though. Any thoughts?

[Zuuljin]

I have a whole book of problems that I used in training for the ACM competition. They range from fun to rediculous and obscure. If there were a thread, i'd dump those on there. =)

[Benito Fireslinger]

and this is why i started codewiki =( too bad i have no time to devote to it

[Bralkan]

I hear leprechauns will write your code if you make it open source.