Background
I've been interested in the game of Sudoku since it became popular a few years ago, and have often daydreamed about what approach one could take to programmatically solve a puzzle. Although I'm not an expert player, when I play I find that I see complex hints about what numbers *must* go here, or *can not* go there. Explaining to another person the logic of each choice would be fairly simple, but coding a straightforward approach for a computer to do the same thing had, until recently, eluded me. I have now successfully licked that problem, and have written a moderately functional solver applet in Java.
This entry takes you through the start-to-finish process of the applet's creation. I decided from the outset not to make this a Swing applet, and to manage event handling and painting directly.
Let's start with the basics of applets, handling screen painting, drawing a board, and creating a framework to draw numbers on individual squares.
Applets
This will not function as a tutorial on the Java programming language, or best practices involving applets, but here is a brief list of things that need to be done to get an applet off the ground quickly:
- Import the Abstract Window Toolkit classes (java.awt.*)
- Extend java.applet.Applet or its subclass javax.swing.JApplet
- Override the init(), paint(), and update() methods
- Compile
- Create an HTML file to load the applet
import java.awt.*;
public class HelloWorldApplet extends java.applet.Applet {
public void init() { }
public void paint(Graphics g){ update(g); }
public void update(Graphics g) { g.drawString("Hello World", 20, 20); }
}The first line imports the AWT package, which lets you draw on a canvas. There are individual classes that handle graphics and image objects, fonts, colors, drawing rectangles and circles, arbitrary shapes, loading and parsing jpeg files, etc. It's easier (lazier) to just grab them all with one import statement.
The class declaration says that I am subclassing java.applet.Applet, the class that presents a canvas to a web browser, and handles client security to prevent you from writing to disk, taking over a user's machine, what have you (see Sun's applet security page).
When an applet is loaded, its init() method is called, followed by the start() method. If the applet is restarted without being unloaded, start() gets called again, but init() does not. This won't be much of a consideration until we get into finishing one game and starting the next, so for now we'll just override init() and leave it at that.
The paint() and update() overrides are a standard trick to reduce flicker. The java.applet.Applet version of update() first clears the canvas, then repaints it, which is the main reason otherwise nice applets flicker.
The standard idiom I use for non-Swing applets is to have paint() just call update(), and have update() do one thing: draw a predefined image (or in this case, a fixed string). All the graphics work will be done outside of the overridden method, followed by a single call to repaint(). This is a technique normally referred to as "double-buffering".
The above code should compile under any modern javac, should you want to test it out. Once compiled, we just need an HTML file with an applet tag to load the class file:
<!doctype html><html><body> <applet width="100" height="50" code="HelloWorldApplet.class"></applet> </body></html>
...and opening that file in a browser will reveal our coveted "Hello World" text that we were so anxious to see. OK, maybe nobody was anxious about it. Anyway, here it is:
Nothing fancy, as expected. What we get from this, however, is a framework we can extend to actually do something interesting.
Drawing the board
To draw the board, the g.drawString above will need to be changed to g.drawImage, and code to declare an Image object and draw to it during initialization will need to be added.
import java.awt.*;
public class DrawBoard extends java.applet.Applet {
Image board; // Image object representing the entire board
public void init() {
board = createImage(451, 451);
Graphics bg = board.getGraphics();
// Step 1 - Draw a grid of light-gray boxes, omitting every third line
bg.setColor(Color.LIGHT_GRAY);
for (int i = 0; i < 10; i++) {
if (i % 3 > 0) {
bg.drawLine(i * 50, 0, i * 50, 450);
bg.drawLine(0, i * 50, 450, i * 50);
}
}
// Step 2 - Use larger black boxes to divide the above grid into 3x3 sections
bg.setColor(Color.BLACK);
for (int i = 0; i < 4; i++) {
bg.drawLine(i * 150, 0, i * 150, 450);
bg.drawLine(0, i * 150, 450, i * 150);
}
}
public void paint(Graphics g){ update(g); }
public void update(Graphics g) { g.drawImage(board, 0, 0, this); }
}Not very different than what we started with. The main additions are in the init() method, where small grey squares and large black squares are drawn via criss-crossing lines spanning the width and height of the canvas. The drawLine() method operates on a graphics object, which allows painting lines, rectangles, circles, and characters onto a canvas or an image object. The drawLine() method takes four arguments, the x and y coordinates of the start and stop point.
In Step 1, I'm drawing 6 horizontal and vertical lines with gaps after each pair. In Step 2, a large Noughts and Crosses board is drawn filling in the gaps.
Two things worth noting there are that drawLine is painting onto the board Image object, not onto the applet's canvas, and that repaint() isn't called since init() occurs before the canvas gets painted. When init() finishes, an initial paint() call will occur automatically. After a game is running, drawing numbers onto the grid will require calling repaint() to get them to appear on the canvas.
The HTML file should also be updated to set the applet's size, and to help the user visually discern where it's boundary is:
<!doctype html>
<html>
<head>
<style>body {background: #ccc; text-align: center;}</style>
<title>Sudoku Bot</title>
</head>
<body>
<applet width="451" height="451" code="DrawBoard.class"></applet>
</body>
</html>After compiling and loading the above file, here is the result:
Drawing numbers
In the above board, the square edges are 50 pixels apart, meaning there are 49 unused pixels between then that can be used to draw numbers or highlight squares with a different background color. The function below can be used as a generic number generator. Pass it a square position (zero indexed), the number to draw, and what color it should be, and it will create a 49x49 pixel image, draw a 25 point number in the middle of it, and attach it to the main board image on the correct square.
public void drawNumber(int x, int y, int num, Color c) {
Image square = createImage(49, 49);
Graphics sg = square.getGraphics();
sg.setColor(c);
sg.setFont(new Font(Font.SANS_SERIF, Font.PLAIN, 25));
sg.drawString(Integer.toString(num), 18, 34);
Graphics bg = board.getGraphics();
bg.drawImage(square, x * 50 + 1, y * 50 + 1, this);
repaint();
}Although workable, there are a few problems with leaving this method as-is. First, we're always going to be using the same font, so it shouldn't be generated each time the method is called. Second, the font isn't anti-aliased, so it looks like this:
The last major issue I see is that there is no error checking to make sure the referenced square exists, or the number to draw is between 1 and 9. Arguably, all 9 numbers should be generated as image objects when the applet initializes, and used as needed, and I may add that functionality later. At this point, I'm not concerned with the overhead of making java draw a digit "from scratch" vs. using predefined tiles. I'm also not going to address error checking just yet, but it's on the to-do list. For now, I've changed the method to use a predefined font, and have turned on anti-aliasing, making the numbers look a little better:
Font f = new Font(Font.SANS_SERIF, Font.PLAIN, 25); // Font for drawing the numbers
public void drawNumber(int x, int y, int num, Color c) {
// Create square image object, populate it with a number roughly in the middle
Image square = createImage(49, 49);
Graphics2D sg = (Graphics2D)square.getGraphics();
sg.setColor(c);
sg.setFont(f);
sg.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
sg.drawString(Integer.toString(num), 18, 34);
// Add this image object to the board, mindful of the gridlines
Graphics bg = board.getGraphics();
bg.drawImage(square, x * 50 + 1, y * 50 + 1, this);
repaint();
}Graphics2D subclasses the Graphics class, hence I can leave the drawNumber method unaltered other than defining the "sg" object, and the addition of the setRenderingHint method. Using this to turn on anti-aliasing gives us a better look to the numbers drawn with a large font:
The last additions to the code for this entry will be to pull the board drawing steps into their own method, and add a "populate" method to throw a few sample numbers into squares to prove that drawNumber() does what it should. Init can then be reduced to descriptive steps:
// Initialize the applet by drawing a Sudoku board, and populating a 3x3 section
@Override
public void init() {
drawBoard();
populate();
}The @Override annotation has also been added, which doesn't affect the way the applet runs at all, but is more of a compile-time hint which, among other things, throws an error if the method doesn't actually override anything.
The populate() method is very straightforward, just iterating through 9 numbers and placing them in the upper-left section of the board:
public void populate() {
int count = 0;
for (int h = 0; h < 3; h++) {
for (int w = 0; w < 3; w++) {
drawNumber(w, h, ++count, Color.red);
}
}
}This makes the applet code thusfar look like this:
import java.awt.*;
public class Sudoku extends java.applet.Applet {
// Initialize the applet by drawing a Sudoku board, and populating a 3x3 section
@Override
public void init() {
drawBoard();
populate();
}
Image board; // Image object representing the entire board
Font f = new Font(Font.SANS_SERIF, Font.PLAIN, 25); // Font for drawing the numbers
/* Standard paint overrides to cut down on flicker. Note that there will be no
controls painted in the applet, just the board image; hence only one thing for
paint and update to do. */
@Override
public void paint(Graphics g){ update(g); }
@Override
public void update(Graphics g) { g.drawImage(board, 0, 0, this); }
public void drawBoard() {
board = createImage(451, 451);
Graphics bg = board.getGraphics();
// Step 1 - Draw a 9x9 grid of light-gray boxes, omitting every third line
bg.setColor(Color.LIGHT_GRAY);
for (int i = 0; i < 10; i++) {
if (i % 3 > 0) {
bg.drawLine(i * 50, 0, i * 50, 450);
bg.drawLine(0, i * 50, 450, i * 50);
}
}
// Step 2 - Use larger black boxes to divide the above grid into 3x3 sections
bg.setColor(Color.BLACK);
for (int i = 0; i < 4; i++) {
bg.drawLine(i * 150, 0, i * 150, 450);
bg.drawLine(0, i * 150, 450, i * 150);
}
}
// Draw number "num" using color c at position x,y, where x and y are between 0 and 8
public void drawNumber(int x, int y, int num, Color c) {
// Create square image object, populate it with a number roughly in the middle
Image square = createImage(49, 49);
Graphics2D sg = (Graphics2D)square.getGraphics();
sg.setColor(c);
sg.setFont(f);
sg.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
sg.drawString(Integer.toString(num), 18, 34);
// Add this image object to the board, mindful of the gridlines
Graphics bg = board.getGraphics();
bg.drawImage(square, x * 50 + 1, y * 50 + 1, this);
repaint();
}
public void populate() {
int count = 0;
for (int h = 0; h < 3; h++) {
for (int w = 0; w < 3; w++) {
drawNumber(w, h, ++count, Color.red);
}
}
}
}... and do this:
What's in that cell?
We need a mechanism to track what number is in each cell, whether it is "owned" by the user or the bot, and a visual cue of whether the square is selected and accepting input. A straightforward way to accomplish this is to use a new class to turn Sudoku cells into objects whose properties can be bundled together. This prevents us from needing several arrays of colors, integers, points, and booleans to manage all the cell properties. Being able to arbitrarily create objects like this is one of the main selling points of Java in the first place, so we should leverage that wherever it is appropriate.
Here is the first draft of the SudokuCell class, which will be compiled separately and included in the jar file that our applet will be running from:
package cea.demos;
import java.awt.Color;
import java.awt.Point;
public class SudokuCell {
Point square;
Color background;
Color fontColor;
int number;
Boolean userAvailable;
public SudokuCell(Point s, Color b, Color f, int n, Boolean a) {
this.square = s;
this.background = b;
this.fontColor = f;
this.number = n;
this.userAvailable = a;
}
}So far, everything is simple. There is one constructor with public attributes that can be directly manipulated. As the applet development progresses, we'll see reasons why this is a bad idea, and we'll lock down the properties better and add some setters and getters (public methods that interact with the class's variables, rather than exposing the variables themselves). But for the sake of simplicity and speed, we'll start with everything being directly accessible.
Drawing the Cell
Back in our main Sudoku class, the drawNumber() method can leverage the new class to simplify its input, and can be expanded to draw the cell's background color in addition to any number that may be in it. Compare the before and after methods:
Before
public void drawNumber(int x, int y, int num, Color c) {
// Create square image object, populate it with a number roughly in the middle
Image square = createImage(49, 49);
Graphics2D sg = (Graphics2D)square.getGraphics();
sg.setColor(c);
sg.setFont(f);
sg.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
sg.drawString(Integer.toString(num), 18, 34);
// Add this image object to the board, mindful of the gridlines
Graphics bg = board.getGraphics();
bg.drawImage(square, x * 50 + 1, y * 50 + 1, this);
repaint();
}Afterpublic void drawCell(SudokuCell c) {
Image cellImage = createImage(49, 49);
Graphics2D sg = (Graphics2D)cellImage.getGraphics();
// Draw background
sg.setColor(c.background);
sg.fillRect(0, 0, 49, 49);
//Draw number
if (c.number > 0) {
sg.setColor(c.fontColor);
sg.setFont(f);
sg.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
sg.drawString(Integer.toString(c.number), 18, 34);
}
Graphics bg = board.getGraphics();
bg.drawImage(cellImage, c.square.x * 50 + 1, c.square.y * 50 + 1, this);
repaint();
}Other than the method's name change, the first thing that should jump out is that the inputs have changed to simply "SudokuCell c". This way, we don't have to be concerned with making sure all the calls to the method have the variables in the correct order. The cell object has everything.
Next, before the number is drawn, the background is filled in by setting the paint color to the cell's background color, then a call to fillRect() to paint the entire cell. Other methods can determine the logic of what the color should be prior to calling drawCell. Lastly, a quick check is done to see if the number is greater than 0 before drawing it. This way, all the cells on the board can be initialized to 0 so that they have a non-null value, and the actual 0 digit won't be displayed.
Now that a mechanism exists to take a cell object and draw it, the board's cell objects can be put into a handy 9x9 array, matching up to their x and y positions on the screen:
SudokuCell cell[][] = new SudokuCell[9][9];
public void initCells() {
// Create 81 cell objects
for (int h = 0; h < 9; h++) {
for (int w = 0; w < 9; w++) {
cell[w][h] = new SudokuCell(new Point(w,h),Color.WHITE, Color.RED, 0, true);
}
}
}Event handlers
In order for the user to be able to set up a board for the bot to solve (or, alternately, solve a board that the bot has set up), the Sudoku applet needs to be able to read mouse and keyboard events. To accomplish this, the java.awt.event.* classes need to be imported, and then three interface classes need to be implemented: MouseMotionListener, which handles move events; MouseListener, which handles click events, and KeyListener, which handles all things keyboard. For each interface, the equivalent event listener needs to be added, and the interface methods must be defined. For example:
import java.awt.*;
import java.awt.event.*; // Import the event classes
public class Test extends java.applet.Applet
implements MouseMotionListener { // Declare the interface to be implemented
// Add the listener to this class
public void init() {
addMouseMotionListener(this);
}
// And finally, define the appropriate methods, and handle them as needed
public void mouseMoved (MouseEvent e) {
// Do stuff
}
public void mouseDragged (MouseEvent e) {
// Do stuff
}
}An interface is simply a list of method definitions. "Implementing" one means defining each method declared in the interface definition. Why you would want to do this may not be intuitive; the basic answer is that something you have no control over is going to be calling everything defined in the interface.In the case of mouse events, a class imports java.awt.Component and calls the addMouseListener method in order to trap mouse events. After that, the class receives calls to methods mouseClicked(), mouseEntered(), mouseExited(), mousePressed(), and mouseReleased() whenever the user performs mouse actions over the component. The class doesn't need to do anything with all the events, but they all need to be defined in order for the listener to not throw an error. The interface helps you avoid that by throwing compile-time errors if all the methods aren't properly declared.
What I would like to do with mouse and keyboard events is manage two modes of input: choosing a cell, and entering a number into a cell. While choosing a cell, I would like the background color of the cell you are hovering on change to yellow, then back to white as your mouse moves to a new cell. When a cell is clicked, the second mode kicks in and the hovering action stops until a number on the keyboard is pressed.
To handle hovering over cells and changing background colors, the mouseMoved() event will suffice. To handle changing modes when a cell is clicked, mouseClicked() will be used. Lastly, receiving the number from the keyboard will be done via the keyTyped() method. This leaves us with seven methods defined in the various interfaces that we don't care about, but that still need to be defined.
Here is the before and after initial first chunk of the Sudoku class
Before
import java.awt.*;
public class Sudoku extends java.applet.Applet {
// Initialize the applet by drawing a Sudoku board, and populating a 3x3 section
@Override
public void init() {
drawBoard();
populate();
}Afterimport java.awt.*;
import java.awt.event.*;
public class Sudoku extends java.applet.Applet
implements MouseMotionListener, MouseListener, KeyListener {
@Override
public void init() {
drawBoard();
initCells(); // (More on this later)
addMouseMotionListener(this);
addMouseListener(this);
addKeyListener(this);
}
// Used event handlers:
public void mouseMoved ( MouseEvent e) {
// Do stuff
}
public void mouseClicked(MouseEvent e) {
// Do stuff
}
public void keyTyped(KeyEvent e) {
// Do stuff
}
// Unused, but required to implement MouseMotionListener
public void mouseDragged (MouseEvent e) { }
//Unused, but required to implement MouseListener
public void mouseExited (MouseEvent e) { }
public void mouseEntered (MouseEvent e) { }
public void mouseReleased(MouseEvent e) { }
public void mousePressed (MouseEvent e) { }
//Unused, but required to implement KeyListener
public void keyPressed (KeyEvent e) { }
public void keyReleased (KeyEvent e) { }Some constants would be useful at this point to define the two input modes, as well as a variable to hold the current mode. Since more than two modes may be used as applet development progresses, integers will be used to declare modes instead of a simple boolean.
static final int CELLBROWSE = 0; static final int CELLGETKEY = 1; int inputMode = CELLBROWSE;
Browse Mode
Browse mode does only one thing: swap background colors. Since swapping background colors can be done in other modes for other reasons, it should be its own method, and mouseMoved() can be extended to the following simple check:
public void mouseMoved (MouseEvent e) {
// No processing unless we're in cell browse mode
if (inputMode != CELLBROWSE) return;
swapCellBackground(e);
}Note that no concern is being made over what cell the mouse is hovering over at this point; the entire mouse event is passed to the swap method. Since the intention is to both set the cell you move into to yellow as well as the cell you move out of to white, a variable needs to exist to hold a reference to the last cell that was set to yellow. Also, a separate method should exist whose only purpose is to locate the current cell the mouse is over, regardless of whether backgrounds are being flipped.
SudokuCell lastCell = new SudokuCell
(new Point(9,9), Color.BLACK, Color.BLACK, 0, false);
public SudokuCell getCell(MouseEvent e) {
int x = e.getX()/50; // Cells are 50 pixels wide
int y = e.getY()/50;
if (x > 8) x = 8; // In case the mouse is in the applet
if (y > 8) y = 8; // but outside of the board
return cell[x][y];
}
public void swapCellBackground(MouseEvent e) {
//Get current cell, no additional processing if the cell hasn't changed
SudokuCell thisCell = getCell(e);
if (thisCell.equals(lastCell)) return;
// Set the old cell's background to white, the new to yellow, then redraw
lastCell.background = Color.WHITE;
thisCell.background = Color.YELLOW;
drawCell(lastCell);
drawCell(thisCell);
lastCell = thisCell;
}GetKey Mode
In this early stage, GetKey mode will be very simple. Clicking a cell not owned by the bot changes the applet to GetKey Mode, and selects that cell, leaving its background yellow. If a key between 1 and 9 is pressed while in this mode, that number appears in red in the selected cell, and the applet switches back to browse mode.
public void mouseClicked(MouseEvent e) {
swapCellBackground(e);
if (lastCell.userAvailable) inputMode = CELLGETKEY;
else inputMode = CELLBROWSE;
}
public void keyTyped(KeyEvent e) {
// No processing unless we're in getkey mode
if (inputMode != CELLGETKEY) return;
// Validate input
char c = e.getKeyChar();
if(c >= '1' && c <= '9') {
lastCell.number = Integer.parseInt(String.valueOf(c));
lastCell.fontColor = Color.RED;
drawCell(lastCell);
inputMode = CELLBROWSE;
}
}Now we have a functioning applet that accepts input and tracks all the cells. The complete source code for both classes can be found here and here, and the working applet is available here.A screenshot of a "game in play" appears below. No checking is done to see if moves made are legal, and no logic exists yet for having the bot attempt to solve the puzzle - both of which we'll conquer next.
Legal moves and solving
Below are some screenshots showing behavior of the bot after adding move checking, a pair of board solving strategies, drawing a "Solve" button, error prompts, and adding cell selection by arrow keys. I'll go into the code shortly, but first here are screenshots of three Sudoku boards whose initial layout I grabbed from various websites. All three have non-ambiguous solutions. Two of them the bot can solve, and one it can not.
Board 1
The board shown here was the first board the bot successfully solved, using a simple "8 of 9" algorithm. When an empty cell's row, column, and 3x3 grid have eight unique digits between them, there is only one digit that will not cause a conflict if placed. In this board, luckily, some 9th digits entered ended up being the 8th digit for another empty cell, so there was a cascade effect until all the cells were filled. A visual explanation may help:
The highlighted cell above can only have one possible value. The column the cell is in already contains 1, 3, 6, 7, 8, and 9 (shown in blue). Additionally it's 3x3 grid contains 2 and 5 (also blue). This leaves 4 as the only possible digit that can be placed in the cell without conflict. That 4, as it happens, becomes the 8th digit for a nearby empty cell:
In this cell, previously 1 and 4 were unaccounted for in the cells row, column, and grid, but now that 4 has been added to the grid, this leaves 1 as the only remaining digit. Wash, rinse, and repeat until the board is solved:
Board 2
This board is not solvable using the 8 of 9 solution method, having too few starting cells ("clue" cells) for that to work. After the bot failed to solve this board, I added a second solution method, similar to the technique that human players use intuitively. The method picks a row, column, or grid, and searches for a number that can only be placed in one of the empty cells. To illustrate:
The highlighted cell above is the only open cell in the middle grid that a 9 can be placed in. The two open cells on top cannot contain a 9 because of the 9 in the right grid, nor the two cells on the bottom because of the 9 in the left grid.
Using a combination of the two solving methods, the bot solves this board without any problems:
There are still boards that have unique solutions that these two techniques alone are not sufficient to solve. Here is one such example:
Board 3
The bot's current solving methods can only deduce the values of a handful of this board's empty cells:
A third method needs to be used to solve boards like this: guessing and backtracking. For example, in the board above, an 8 can be placed in two possible open cells in the upper-left grid. If the bot could remember the state of the board, and pick one of the two cells, it could see if that path leads to a solution, and if not, reload the board and pick the other path.
Unfortunately that method will take some additional code refactoring, as I did not design the bot with that in mind. (As a software developer, I'm very familiar with this situation... if I had a nickel for every new requirement that caused me to retrofit a project or redo it from scratch...)
So those are the fun screenshots. A link to the applet's current version is at the bottom of this page, or you can continue reading how I tackled checking for legal moves and writing solving algorithms.
Legal Moves
As in earlier versions of the applet, a two-dimensional array of SudokuCell objects is declared and initialized so that the x and y of the array match the x an y position on the board.
// Grid representing the board itself
SudokuCell board[][] = new SudokuCell[9][9];
public void initCells() {
// Create 81 cell objects
for (int h = 0; h < 9; h++) {
for (int w = 0; w < 9; w++) {
board[w][h] = new SudokuCell(new Point(w,h),Color.WHITE, userColor, 0, true);
}
}
currentCell = board[0][0];
}Newly added to the applet are two-dimensional arrays representing each row, column and grid, and what cells contain each number. These won't be created as new objects, but will instead contain references to the board[][] objects as numbers are put in play.
/* Grids where x is an entire column, row, or 3x3 grid, and y+1 is a number in play on that grid. These will be references to the 9x9 board above, and exist only to speed up searches for legal moves and cross-referencing for solution searching. */ SudokuCell xGroup[][] = new SudokuCell[9][9]; SudokuCell yGroup[][] = new SudokuCell[9][9]; SudokuCell gridGroup[][] = new SudokuCell[9][9];
The first dimension of these arrays refers to the row, column, or grid number. xGroup[0] refers to the board's first column. The second dimension refers to which number. The cell containing the number 1 in the first column would be xGroup[0][0].
These objects start out uninitialized, so to check if the the number 1 has been played in the left column, I simply need to check whether or not xGroup[0][0] is null. If it is, 1 hasn't been played. If it's not, the cell object that gets returned will contain the x and y board position of the cell.
To add a cell, then, I need to determine from it's board coordinates what the row, column, and grid numbers are, and then check the three group references to see if the number has already been played somewhere that would conflict.
String promptMsg = ""; // Shown when moves are illegal, and after bot tries to solve
// Check the row, column, and 3x3 grid to see if n is already in play
public boolean checkGroups(SudokuCell c, int index) {
promptMsg = "";
int n = index + 1; // group indices are 0 indexed, but refer to 1 through 9
if (n < 1 || n > 9) {
promptMsg = "Number must be between 1 and 9";
return false;
}
if (cellExists(xGroup[c.square.x][index])) {
promptMsg = "Number " + n + " already used in this column";
return false;
}
if (cellExists(yGroup[c.square.y][index])) {
promptMsg = "Number " + n + " already used in this row";
return false;
}
if (cellExists(gridGroup[c.gridGroup][index])) {
promptMsg = "Number " + n + " already used in this 3x3 grid";
return false;
}
return true;
}
public Boolean cellExists(SudokuCell c) {
if (c == null) return false;
// If bot is solving board, dispense with extra handling and just return true
if (inputMode == SOLVEBOARD) return true;
// Unselect currentCell, set it's background to white, and redraw it
currentCell.selected = false;
currentCell.background = Color.WHITE;
drawCell(currentCell);
// Set the cell in conflict to a cyan background
c.background = Color.CYAN;
c.selected = false;
drawCell(c);
errorCell = c;
return true;
}If false is returned from checkGroups(), promptMsg will be shown to the user by the calling method. If true is returned, the move is legal to make. cellExists() checks whether of not the cell reference is null. If it isn't null, the cell in question is highlighted in cyan to show the user why the number can't be played. The effect looks like this:
Now all that is needed is a means of adding to and subtracting from these groups:
int cellsInPlay = 0; // How many cells have numbers in them. Game ends at 81
// Remove a cell's number from the row, column, and 3x3 grid it is on
public void subtractFromGroups(SudokuCell c) {
if (c == null || c.number == 0) { return; }
int n = c.number - 1;
xGroup[c.square.x][n] = null;
yGroup[c.square.y][n] = null;
gridGroup[c.gridGroup][n] = null;
cellsInPlay--;
}
// Attempt to add a number to a cell.
public boolean addToGroups(SudokuCell c, int n) {
// Nothing to do if the number being added is the one already in the cell
if (c.number == n) return true;
int index = n-1;
if (!checkGroups(c, index)) return false;
// If overwriting an existing number, remove it from groups first
if(c.number > 0) { subtractFromGroups(c); }
xGroup[c.square.x][index] = c;
yGroup[c.square.y][index] = c;
gridGroup[c.gridGroup][index] = c;
c.number = n;
cellsInPlay++;
return true;
}And now we have a comprehensive means of checking for legal moves that both the user and bot can use. Best of all, there is no iterating through arrays or collections involved, a modest speedup at the cost of some extra memory.
It's pretty straightforward how the column and row groups are determined (they just follow the x and y coordinates of the cell, respectively), but some explanation is in order regarding the new object variable "gridGroup". Here is the latest revision of the SudokuCell class, which will help explain:
package cea.demos;
import java.awt.Color;
import java.awt.Point;
public class SudokuCell {
Point square;
Color background;
Color fontColor;
int number;
Boolean userAvailable;
int gridGroup;
Boolean selected;
public SudokuCell(Point s, Color b, Color f, int n, Boolean a) {
this.square = s;
this.background = b;
this.fontColor = f;
this.number = n;
this.userAvailable = a;
this.gridGroup = (s.y/3) * 3 + (s.x/3);
this.selected = false;
}
}The gridGroup variable is calculated when the object is created, using a handy feature of integers: dropping the remainder when you divide. Grids 0, 1, and 2 are the top three grids, 3, 4, and 5 are the middle three, and 6, 7, and 8 are at the bottom. Also new to the class is the "selected" variable, which indicates to the cellDraw method whether or not to draw an underline in the cell image. The Sudoku class assures that only one object is selected, but the object model itself does not - more bad mojo that I may come back and clean up later.
Solving a board
Here is a method used in the "8 of 9" solving technique. It takes a cell reference, and counts the number of unique digits in play in the three groups around it, keeping track of the last unplayed digit. If there were 8 unique digits already in play, then "number" is the ninth. (Or rather, "number + 1" is, since the groups are zero-indexed.)
public int findNinth(SudokuCell c) {
if (c.number > 0) return 0; // Only operate on empty squares
int size = 0;
int number = -1;
for (int n = 0; n < 9; n++) {
if (xGroup[c.square.x][n] != null || yGroup[c.square.y][n] != null
|| gridGroup[c.gridGroup][n] != null) {
size++;
} else {
number = n;
}
}
return size == 8 ? number + 1 : 0;
}Here is the board solving algorithm employing only that technique. It basically iterates through all the empty cells and tries to "findNinth" on them in a loop until either all 81 are filled in, or an iteration completes with no new cell being added.
public void boardSolve() {
boolean cellAdded;
int addNumber;
SudokuCell c;
while (cellsInPlay < 81) {
cellAdded = false;
for (int h = 0; h < 9; h++) {
for (int w = 0; w < 9; w++) {
c = board[w][h];
addNumber = findNinth(c);
if(addNumber > 0) {
c.fontColor = botColor;
c.userAvailable = false;
// Break if the "finder" returns a number that can't be added
if(!addToGroups(c, addNumber)) return;
drawCell(c);
cellAdded = true;
}
}
}
if (!cellAdded) {
prompt("Could not solve");
return;
}
}
prompt ("Solved!");
}The "number can only be placed in one cell" method is more involved. The checkEmpties() method below receives an arbitrary ArrayList of cells, then builds a hash of digits where the values are either the only cell the digit can be placed, or are the "nullCell" object, if a digit can be placed in more than one cell.
The method then iterates through the hash, and for each digit not pointing to nullCell, the digit is placed in the appropriate cell. For to be thorough, even though the method previously checked each cell to see if the digit could be put there, the method throws an error if the attempt to actually place the digit fails.
// Refers to an object that can be put in a hash representing a cell not on the board
SudokuCell nullCell = new SudokuCell(new Point(9,9), botColor, botColor, 0, false);
/* Take a group of cells, check the empty cells to see what can be added to them.
Look for digits that can only be added to one cell, and add the digit there */
public boolean checkEmpties(ArrayList cells) throws Exception {
HashMap<Integer, SudokuCell> digits;
SudokuCell c;
boolean cellAdded = false;
int index;
/* Get hash of key = digit, value = cell it can be placed in.
If value = null, digit is already in use. If value = nullCell,
more than one digit can be placed in cell*/
digits = new HashMap<Integer, SudokuCell>();
Iterator i = cells.iterator();
while (i.hasNext()) {
c = (SudokuCell)i.next();
for (index = 0; index < 9; index++) {
if (checkGroups(c, index)) {
if (digits.containsKey(index)) digits.put(index, nullCell);
else digits.put(index, c);
}
}
}
// Iterate through hash keys, add numbers to appropriate cells
i = digits.keySet().iterator();
int n;
while(i.hasNext()) {
index = (Integer)i.next();
n = index + 1;
c = (SudokuCell)digits.get(index);
if (!c.equals(nullCell)) {
c.fontColor = botColor;
c.userAvailable = false;
if(!addToGroups(c, n)) {
c.background = Color.CYAN;
drawCell(c);
throw new Exception("Couldn't add " + n + " to cell");
}
drawCell(c);
cellAdded = true;
}
}
return cellAdded;
}The nice thing about this method is that it doesn't care where on the board these cells are, making it simpler to modify the applet to handle nonstandard board layouts, where "grids" are not uniform 3x3 set of cells.
Finally, the boardSolve() method needs to be extended to use this method, passing it ArrayLists that encompass each row, column, and grid.
public void boardSolve() {
boolean cellAdded;
int addNumber;
SudokuCell c;
while (cellsInPlay < 81) {
cellAdded = false;
/* Pass one. For each empty cell, check the total number of unique
digits in the cell's grid, row, and column. If the total is 8,
the unused digit belongs in the empty cell. */
for (int h = 0; h < 9; h++) {
for (int w = 0; w < 9; w++) {
c = board[w][h];
addNumber = findNinth(c);
if(addNumber > 0) {
c.fontColor = botColor;
c.userAvailable = false;
// Break if the "finder" returns a number that can't be added
if(!addToGroups(c, addNumber)) return;
drawCell(c);
cellAdded = true;
}
}
}
/* Pass two. For each column's empty cells, check what digits can legally
be added to each cell. When a digit can only be added to one cell in
the column, put it there. */
if (cellsInPlay < 81) {
ArrayList<SudokuCell> cells = new ArrayList<SudokuCell>();
try {
for (int column = 0; column < 9; column++) {
cells.clear();
for (int n = 0; n < 9; n++) {
c = board[column][n];
if (c.number == 0) cells.add(c);
}
if (checkEmpties(cells)) cellAdded = true;
}
// Do the same for rows
if (cellsInPlay < 81) {
for (int row = 0; row < 9; row++) {
cells.clear();
for (int n = 0; n < 9; n++){
c = board[n][row];
if (c.number == 0) cells.add(c);
}
if (checkEmpties(cells)) cellAdded = true;
}
}
// And for grids
if (cellsInPlay < 81) {
for (int grid = 0; grid < 9; grid++) {
cells.clear();
for (int n = 0; n < 9; n++) {
int x = (grid%3) * 3 + (n%3);
int y = (grid/3) * 3 + (n/3);
c = board[x][y];
if (c.number == 0) cells.add(c);
}
if (checkEmpties(cells)) cellAdded = true;
}
}
} catch (Exception e) {
prompt(e.getMessage());
return;
}
}
if (!cellAdded) {
prompt("Could not solve");
return;
}
}
prompt ("Solved!");
}There are a few modifications implied by these methods that I haven't discussed, and many improvements that could still be made. I might continue to work on the bot to clean up code, improve the object model, and handle the backtracking solving method I referred to earlier, or I may leave it as is. Either way, here is a link to the working applet as it stands, here is the main applet's source code, and here is the cell object source code.
No comments:
Post a Comment