I wrote my own Sudoku solver a few weeks ago; it works fine on easy and
medium Sudokus but fails on harder ones because it is only doing elementary
solving, i.e. doing intersections between the available numbers for the row,
column, and block. There are, however, various situations that require more
sophisticated logic than just the intersections so you should be prepared
for a fair bit of coding if you want to solve *all* Sudokus rather than just
the easiest ones :-)

With that observation out of the way, my Sudoku solver made heavy use of
collections, specifically Sets using the HashSet implementation, and only
minor use of standard arrays. The structures available within collections
are easily manipulated and the syntax to work with them is quite concise.
Since you didn't mention any collections in your question, you may not be
familiar with them; if that is the case, take a look at the Collections
trail in the Java Tutorial. Here is the URL:
http://java.sun.com/docs/books/tutorial/collections/index.html

I understand that the smaller 3 x 3 grids within the Sudoku are properly
called "Regions". I found that I needed to write two methods to work with
Regions:
- getRegionBoundaries()
- getRegionLocation()

The getRegionBoundaries() method takes the horizontal and vertical position
of a region within the Sukoku as input and returns the corners of the
region. Therefore, if the input is (2,2) [NOTE: I use 0-based numbering for
my arrays and array-like structures], meaning the rightmost, lowest region
of the Sudoku, i.e.  the method comes back with (6, 6, 8, 8), meaning that
the region has (6, 6) as its upper left corner and (8, 8) as its lower left
corner. You can easily get the outputs from the inputs with simple if
statements: if the regionHorizontalPosition = 0 {lowRow = 0; highRow = 2;}
and so forth.

The getRegionLocation() method takes the horizontal and vertical position of
a square within the Sudoku as input and returns the location of the region
on the Sudoku. Therefore, if the input is (5, 3), meaning the 4th square
from the left on the 6th row of the Sudoku, the method should return (1, 1),
meaning the center region of the Sudoku.

Those two methods enabled me to quickly determine what region was associated
with a given square and where that region was situated on the Sudoku
relative to the others. That made solving the Sudoku fairly straightforward.

There are probably several good ways to solve Sudokus so don't be too
worried if your solution is different from the solutions of any of the other
people who have built solvers. I think you've picked a good project to get
reaquainted with Java and should have ample opportunity to learn more about
looping and using collections. You also have several opportunities to use OO
to help you define classes that make the program easier.

Good luck,

Rhino

   Definitely not an array. Arrays are generally fixed-size, so removing or
inserting elements into it is non-trivial. A Vector is actually a special
kind of List, but for what you need (insertion and deletion from arbitrary
points), a List is all you need. You could use an Array if you wanted to, or
you could use any other implementation of List (e.g. ArrayList, LinkedList,
etc.)

   If I understand you correctly, you're thinking of the Sudoku puzzles
where there's a 3x3 grid of "regions", where each region is a "3x3" grid of
cells (each cell contains 1 number in the final solution), so that there are
81 cells in all.

   It sounds like you want to iterate over the cells in a region is a
specific order, but I don't yet understand what order it is you're trying to
achieve. If the order is relatively fixed, you might want to look at the
Iterable and Iterator interfaces:

http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Iterable.html
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Iterator.html

   As Rhino mentioned in another post, you should study Sun's Collections
API. I think a good design might be to treat your Sudoku grid as a
collection of regions, where each region is a collection of cells, where
each cell is a collection of numbers. And "solving" the grid means removing
numbers from the cells until each cell contains exactly 1 number.

   - Oliver

---------
An ArrayList would work just fine here.
----------

-----
Since you want easier insertions and deletions at any point of your
"list", you would use an ArrayList. So it would be an ArrayList inside
an Arraylist. For simplicity, you can have 9 separate arrayLists,
instead of (ArrayList inside ArrayList inside ArrayList). Avoid 3
dimensionality for simplicity, as of now, IMHO.
-----

How about boolean[9] to track which numbers are still there? That will
be fast.

Thank you all for the informative replies.