How I Immersed Myself in GridWorld
Sudoku has rapidly become a new craze, and with the introduction of GridWorld, I couldn't resist trying to build an electronic simulation of the daily newspaper puzzle. Creating a sudoku program required me to learn the various parts of GridWorld.
The Basic Grid
First, I made the basic grid. Sudoku uses a nine-by-nine grid of cells containing Integer objects. This required extending the World class, the mediator between a grid and the GridWorld graphical user interface (GUI). Building the basic grid was simple; I constructed a BoundedGrid of size nine by nine containing Integer objects. Then I gave the sudoku world this grid as its environment using the setGrid method.
The Initial Board
Next, I made the initial board with the opening numbers. The first problem was how to make Integer objects appear in a location. The put method in Grid solved this part easily, with the two parameters being the location and the object to be put in that location. A Grid knows to display the value of an Integer as its String equivalent. After that, I had no difficulty coming up with a method to read the opening board from an input file.
Sample Partial Code Segments
private static Grid‹Integer› grid = new BoundedGrid‹Integer›(9, 9);
public static void setDefaultGrid()
{
for (int i = 0; i ‹ 9; i++)
for (int j = 0; j ‹ 9; j ++)
grid.put(new Location(i, j), 0);
}
public static void main(String[] args)
{
setDefaultGrid();
World‹Integer› world = new SudokuRunner();
world.setGrid(grid);
world.show();
}
Allowing Player Input
The next step was to allow the player to start solving the puzzle. To do this, I needed the program to add an Integer to empty cells. I solved this by overriding the locationClicked method in World to show an input dialog box when the player clicks on any empty cell. Empty cells were determined with a call to the get method of Grid. Any cell that returned a null value was empty. The program checks that the value typed by the player falls within the required range (from 1 to 9) and then puts that value in the spot the player clicked.
Checking for a Winner
With each new addition to the board, the program has to determine if the player has reached the winning solution. This first requires verifying that all empty cells are filled. If so, the next step is to evaluate the current board configuration -- is it a winner? According to the standard rules for sudoku, a winning board has the numbers 1 through 9 -- in any order -- in every row, every column, and every subgrid (three-by-three box). I needed an easy way to find out if any of the numbers are duplicates. The simplest approach was to add each Integer from the row/column/subgrid to a set and check the size of the resulting set. A winning solution returns a size of 9 for each row, column, and subgrid.
So Far, So Good, But . . .
The first problem I found with this draft was that I could not change the value in a location if I did not reach a winning solution on the first attempt. I also had not achieved the traditional look of the sudoku board with the subgrids clearly marked. I decided to use color to solve both problems.
The STile Object
I realized that it was not enough to just add Integer objects to a given location. I needed a more sophisticated object, one with a value and a color. Thus, the STile was born. With the getColor and getText methods, Grid could display both properties of each STile. I could now make the subgrids by using alternating colors for each three-by-three grid. I could also differentiate between locations containing the opening numbers (which cannot change) and locations that the player fills (which the player can change if he or she does not reach a winning solution).
Sudoku: The End of the Journey?
And here ended the quest to make a simple sudoku program. What next? Well, that's up to you.
Ann Shen is a computer science teacher at Bishop Strachan School in Toronto. She is a Reader for the AP Computer Science Exam and a member of the AP Computer Science Development Committee.
|
Course Home Pages