Page 1 of 1

Sudoku I - Basic tools Utilities to build Sudoku application Rate Topic: -----

#1 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Posted 19 October 2010 - 09:30 PM

This is the first of my Sudoku tutorials. I have 5 or 6 planned.
Now if you thing that I will provide you right away with a complete Sudoku solver, you are not at the right place (may be it will come eventually).

I will provide you with classes that you will most probably edit to suit your needs.
Many methods included in the following classes are not used by the actual posted applications they are just there for your use to to build your own Sudoku solver.

The next tutorial will have a brute force Sudoku solver (as a console application) the following tutorial will have some GUIs to show and display the results.

OK let's start with the basic concepts, and right away, to make the code work, I woul have to ask you to insert a GUI component to the code. I will come to it a little later.

OK, the first class is the Cell class. As we will later make a GUI, a made the Cell class to extend the JLabel class.

This class is responsible to display a Sudoky cell, so obviously, for the GUIs a JLabel.
JLabel, by default are NOT focusable, do not have MouseListener, do not have KeyEvent listener, but this class implements all these (It will be usefull later when we will have a GUI).

So here is Cell.java a lot of comments in the code should explain what it is doing

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

/*
 * A Sudoku cell as it might be used in a GUI make it a JLabel
 * by extending the JLabel class
 */
public class Cell extends JLabel implements FocusListener, MouseListener, KeyListener {
	
	private static final long serialVersionUID = 1L;
	// the font use for displaying the label
	private static Font labelFont, boldFont;
	// the background for the cell that hasfocus
	private static Color lightYellow = new Color(255, 255, 125);
	
	// at first invocation create our fonts
	static {
		JLabel l = new JLabel();          	// build a temp label to get standard font
		Font font = l.getFont();			// get the Font
		// make a font 2 times the original size (which will be considered bold)
		boldFont = font.deriveFont(font.getStyle(), (int) (font.getSize2D() * 2.0));
		// a smaller font for the cell not part of the original problem
		labelFont = boldFont.deriveFont(boldFont.getStyle() ^ Font.BOLD);	
	}
	// the String representation of the point 
	private String str;
	// the value of the cell
	private int value;
	// if the value is part of the original problem
	private boolean originalProblem;
	// the cell position
	private Point point;
	
	// an ArrayList to register the SudokuCellKbListener that want to be informed when a
	// a the keyboard is press
	private ArrayList<SudokuCellKbListener> listenerList;
	
	/*
	 * Constructor
	 */
	public Cell(int x, int y) {
		super("     ");
		point = new Point(x, y);
		str = String.format("(%02d,%02d)", x, y);
		// have the number centered
		setHorizontalAlignment(SwingConstants.CENTER);
		// make it opaque to it will have a background
		setOpaque(true);
		setBackground(Color.WHITE);
		// give it a border
		setBorder(BorderFactory.createLineBorder(Color.BLACK));
		// the font to use
		setFont(labelFont);
		// the arrayList for the listener of the keyboard
		listenerList = new ArrayList<SudokuCellKbListener>();
	}
	
	/*
	 * Returns the cell value
	 */
	public int getValue() {
		return value;
	}
	/*
	 * Returns cell position (mostly for debug purpose)
	 */
	public Point getPosition() {
		return point;
	}
	
	/*
	 * Reset a cell 
	 */
	private void reset(int val, boolean original) {
		value = val;
		// if value == 0 we put originalProblem to false and set the label at " "
		if(value == 0) {
			originalProblem = false;
			setText("     ");
			return;
		}
		originalProblem = original;
		setText("  " + Integer.toString(value, Character.MAX_RADIX).toUpperCase() + "  ");	
		// determine the font based on the type
		if(originalProblem)
			setFont(boldFont);
		else
			setFont(labelFont);
	}
	/*
	 * Set the value for an original problem
	 */
	public void setOriginalProblemValue(int value) {
		reset(value, true);
	}
	/*
	 * Set the value for a user guess or solver
	 */
	public void setValue(int value) {
		reset(value, false);
	}
	// getter for the type of value
	public boolean isOriginalProblem() {
		return originalProblem;
	}
	/*
	 * The method that overloads toString() that return the value 
	 */
	public String toString() {
		// for text display so we also pass the 0
		return Integer.toString(value, Character.MAX_RADIX).toUpperCase();	
	}
	/*
	 * To return the unique Id as a String
	 */
	public String getIdStr() {
		return str;
	}
	
	/*
	 * The two method invoked when the cell gain or loose focus
	 */
	@Override
	public void focusGained(FocusEvent e) {
		setBackground(lightYellow);
	}
	@Override
	public void focusLost(FocusEvent e) {
		setBackground(Color.WHITE);
	}

	/*
	 * The mouse listener to gain focus when a cell is cliked
	 * only pressed is used
	 */
	@Override
	public void mousePressed(MouseEvent e) {
		requestFocusInWindow();				// give focus to that cell
	}
	public void mouseClicked(MouseEvent e) {}
	public void mouseEntered(MouseEvent e) {}
	public void mouseExited(MouseEvent e) {}
	public void mouseReleased(MouseEvent e) {}

	/*
	 * to register to have the keyboard event relayed
	 */
	public void registerCellKbListener(SudokuCellKbListener listener) {
		// at the first call, when the arrayList is empty, register this as keyLlistener
		// to react to keyBoard key pressed and make the cells focusable
		if(listenerList.size() == 0) {
			// labels by default are not focusable make it focusable
			setFocusable(true);
			// and add them a focus listener so we can change the background color
			addFocusListener(this);
			// amouse listener to be able to select the cell by clicking over it with the mouse
			addMouseListener(this);
			addKeyListener(this);
			// disable the fact that a TAB will bring me to next JLabel
			setFocusTraversalKeysEnabled(false);
		}
		// add this listener to our list
		listenerList.add(listener);
	}
	/*
	 * The KeyListener methods
	 */
	@Override
	public void keyPressed(KeyEvent ev) {
		// pass through our list to prevent all the possible listener
		for(SudokuCellKbListener listener : listenerList) {
			listener.keyPressed(this, point.x , point.y, ev);
		}
	}
	public void keyReleased(KeyEvent e) {}
	public void keyTyped(KeyEvent e) {}
}




Now if you try to compile that code you will have an error saying that SudokuCellKbListener is missing. This is an interface. This interface is used for GUI components to register themselves to the Cell class so they will be informed if a keyborad action happened on that cell

So for your code to compile, you need the SudokuCellKbListenr interface, we will see it in more details later (n the first tutorial about the GUIs)
So here it is, just cut & paste it without asking question for now

SudokuSellKbListener.java

import java.awt.event.KeyEvent;

/*
 * An interface that will implement the GUI components that want to be
 * informed when a key is pressed on the GUI
 */
public interface SudokuCellKbListener {

	// the cell will call this method when a character will be pressed 
	// when they have focus
	public void keyPressed(Cell cell, int x, int y, KeyEvent e);
}



Next a Sudoku within its Grid has Row, Column and Region.
All the rules, about is a cell is available, if there are twins,... apply to the same array of cells that are Row, Column and Region. It would be a wate of time to see if a cell is used in different row, column and region. We have to create a class that represent all of them. For a 9X9 Sudoku, the row, column, and region will contains 9 cells, these 9 cells are the SAME (pointing to the original grid cells)

Here is RowColRegion.java
/*
 * Contains an array of N Sudoku Cells that represents a Row, a Column or a Region
 * The whole idea is to have a common class to describe one of the 3 components
 * Common methods can check for unicity of a number in a Row, Column, Region whitout
 * having to know if the array of cells passed as parameter are effectively a Row,
 * a Column or a Region.
 * 
 * It is in that class that you should check bor twins, 3 of a kinds, ....
 */
public class RowColReg {

	// The array of Sudoku cells
	private Cell[] cell;
	
	/*
	 * Constructor
	 */
	public RowColReg(Cell[] array) {
		cell = array;
	}
	
	/*
	 * If the RowColRegion contains the value
	 */
	public boolean contains(int n) {
		for(int i = 0; i < cell.length; i++) {
			if(cell[i].getValue() == n)
				return true;
		}
		return false;
	}
	/*
	 * Returns if the value pass as parameter is valid for that RowColReg
	 */
	public boolean isAvailable(int n) {
		// always permit to set the cell to 0
		if(n == 0)
			return true;
		return !contains(n);
	}
	/*
	 * Mostly for debug purpose a representation of the whole array
	 */
	public String toString() {
		String str = "[" + cell[0].getIdStr();
		for(int i = 1; i < cell.length; i++)
			str += " " + cell[i].getIdStr();
		return str + "]";
	}
	
	/*
	 * For the GUIs to receive the cells
	 */
	Cell[] getCells() {
		return cell;
	}
}


And finally the Grid that contains all of these.
For a 9x9 Sudoku the Grid will contains 9 RowColReg as row, 9 RowColReg as column and 9 RowColReg as regions. But all these RowColReg will reference (point to) the same Cell in the grid array of cells.

The Grid class has a main() method that verify that all the stuff works correctly printing the coordinates of all Cells in row, column, region

The clas Grid.java

import java.awt.*;
import java.awt.event.*;
import java.util.*;
/*
 * A class that implements a Sudoku grid 9 X 9
 * array contains an array of 9 x 9 cells
 * row, column and region are arrays[9][9] that reference the SAME cells that are in array
 */
public class Grid implements SudokuCellKbListener {

	// The dimension of the grid
	private int size;
	// The array of Cell
	private Cell[][] cell;
	// To access by column by row and by region
	private RowColReg[] column, row, region;
	// The region of each cell
	private int[][] regionId;

	/*
	 * Constructor that receives the size of the Grid as parameter
	 */
	public Grid(int size) {
		// validate the suported size
		switch(size) {
			case 4:
			case 9:
			case 16:
			case 25:
				break;
			default:
				throw new IllegalStateException("Gid size available values are 4, 9, 16, 25");
			
		}
		
		this.size = size;
		// create the master grid and fill it
		cell = new Cell[size][size];
		regionId = new int[size][size];
		for(int col = 0; col < size; col++) {
			for(int row = 0; row < size; row++) {
				cell[row][col] = new Cell(row, col);
			}
		}

		// the rows are easy we just use the rows of the grid as Java 2 dimensionnal arrays
		// are just and aray of arrays
		row = new RowColReg[size];
		for(int i = 0; i < size; i++)
			row[i] = new RowColReg(cell[i]);

		// for columns it is more complicated we have to select each element as they do not
		// follow each other in memory
		column = new RowColReg[size];
		for(int i = 0; i < size; i++) {
			Cell[] c = new Cell[size];
			for(int j = 0; j < size; j++) {
				c[j] = cell[j][i];  // all the rows of that column
			}
			column[i] = new RowColReg(c);
		}

		// now the regions the most complicated ones
		region = new RowColReg[size];
		// this will be the index of the region[] we are building
		int k = 0;
		// the number of rows (and columns) for the number of region
		int nb = (int) Math.sqrt((double) size);
		// the cells of the region
		Cell[] c;
		// lets fill them
		for(int i = 0; i < nb; i++) {
			// first row ow that region
			int firstRow = i * nb;
			for(int j = 0; j < nb; j++) {
				// first col of that region
				int firstCol = j * nb;
				// the cells of that region
				c = new Cell[size];
				// index in that array of Cells
				int idx = 0;
				for(int rRow = 0; rRow < nb; rRow++) {
					for(int rCol = 0; rCol < nb; rCol++) {
						c[idx++] = cell[firstRow+rRow][firstCol+rCol];
					}
				}
				// build the RowColReg object from that array
				region[k] = new RowColReg(c);
				// build the regionId for these cells (could have been integrated in the
				// previous loop but complicated for nothing lots clearer, from a code
				// point of vue, here)
				for(int cellId = 0; cellId < c.length; cellId++) {
					Point p = c[cellId].getPosition();
					regionId[p.x][p.y] = k;
				}
				// next region
				k++;
			}
		}
	}

	/*
	 * returns the all the available value for a cell
	 */
	public int[] getAllAvailableValues(int x, int y) {
		// build a BitSet from 0 to size+1 (0 won't be used)
		BitSet bs = new BitSet(size + 1);
		for(int i = 1; i <= size; i++) {
			// if i is available for that cell
			if(isAvailable(x, y, i))
				bs.set(i);
		}
		// plus obviously its actual value
		int value = getValue(x, y);
		if(value > 0)
		   bs.set(value);
		// make an array of int out of the BitSet
		return buildArray(bs);
	}
	
	/*
	 * returns the the available value for a cell
	 * which has not been set as an original value or set by the user
	 */
	public int[] getAvailableValues(Point p) {
		int x = p.x;
		int y = p.y;
		// if set as original or by the user return an empty array
		if(cell[x][y].isOriginalProblem())
			return new int[0];
		// build a BitSet from 0 to size+1 (0 won't be used)
		BitSet bs = new BitSet(size + 1);
		for(int i = 1; i <= size; i++) {
			// if i is available for that cell
			if(isAvailable(x, y, i))
				bs.set(i);
		}
		// plus obviously its actual value if it not 0
		int value = getValue(x, y);
		if(value > 0)
		   bs.set(value);
		// make an array of int out of the BitSet
		return buildArray(bs);
	}
	
	/*
	 * Makes an array of int from bit set to ON in the BitSet received as parameter
	 */
	private int[] buildArray(BitSet bs) {
		// get the number of bit set to on
		int nb = bs.cardinality();
		// if none no neeed to loop
		if(nb == 0)
			return new int[0];
		// build the array
		int[] array = new int[nb];
		// index in the new array
		int k = 0;
		for(int i = 1; i <= size; i++) {
			// if the bit is set
			if(bs.get(i))
				array[k++] = i;	// add it to the array
		}
		return array;
	}
	/*
	 * Returns if the value N can be set in x,y 
	 */
	public boolean isAvailable(int x, int y, int n) {
		if(!row[x].isAvailable(n))
			return false;
		if(!column[y].isAvailable(n))
			return false;
		if(!getRegion(x, y).isAvailable(n))
		    return false;
		return true;
	}

	/*
	 * to throw an exception is value not valid
	 */
	private void validate(int x, int y, int value) {
        // reset to 0 always ok
		if(value == 0)
			return;
		// if value already the one there
		if(value == getValue(x, y))
			return;
		// if greater than size or not available 
		if(value > size || !isAvailable(x, y, value))
			throw new IllegalStateException("Trying to set " + value + " at x: " + x + " y: " + y);		
	}
	/*
	 * Set the value for an original problem
	 */
	public void setOriginalProblemValue(int x, int y, int value) {
		validate(x, y, value);
		cell[x][y].setOriginalProblemValue(value);
	}
	/*
	 * Set the value for a user guess
	 */
	public void setCellValue(int x, int y, int value) {
		validate(x, y, value);
		cell[x][y].setValue(value);
	}
	// getter for the type of value
	public boolean isOriginalProblem(int x, int y) {
		return cell[x][y].isOriginalProblem();
	}

	// to get the column, the row of the region of a cell
	// for the row and column it is quite evident for the region it is trickier
	// we standardize the methods by making one for each type of RowColReg
	public RowColReg getRow(int x, int y) {
		return row[x];
	}
	public RowColReg getColumn(int x, int y) {
		return column[y];
	}
	public RowColReg getRegion(int x, int y) {
		return region[regionId[x][y]];
	}

	/*
	 * To get a cell value
	 */
	int getValue(int x, int y) {
		return cell[x][y].getValue();
	}
	int getValue(Point p) {
		return getValue(p.x, p.y);
	}
	/*
	 * For the brute force return the list of the cells to fill
	 */
	public ArrayList<Point> getCellsToFill() {
		// ArrayList of cell coordinates stored as Point that will be returned
		ArrayList<Point> al = new ArrayList<Point>();
		// scan all cells
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				// if its value is 0
				if(cell[i][j].getValue() == 0)
					al.add(cell[i][j].getPosition());  // add its Point object
			}
		}
		return al;
	}
	/*
	 * To print the grid
	 */
	public void printGrid() {
		// where to separate region
		int mod = (int) Math.sqrt((double) size);
		// the line of +-----+-----+------- to separate regions in vertical display
		StringBuilder sb = new StringBuilder(size * 5);
		sb.append(' ');
		for(int i = 0; i < mod; i++) {
			sb.append("+-");
			for(int j = 0; j < mod * 2; j++) {
				sb.append('-');
			}
		}
		sb.append('+');
		String line = sb.toString();
		
		// for every row
		for(int i = 0; i < size; i++) {
			if(i % mod == 0)
				System.out.println(line);
			// for every column
			for(int j = 0; j < size; j++) {
				// if module sqrt of the grid
				if(j % mod == 0)
					System.out.print(" |");
			    System.out.print(" " + cell[i][j]);		
			}
			// the final "|" at the end of the row
			System.out.println(" |");
		}
		// the final +------+-----------
		System.out.println(line);
	}
	
	/*
	 * For the GUIs to get the region
	 */
	public RowColReg[] getRegion() {
		return region;
	}

	/*
	 * To ask the Grid to Register as a SudokuCellKbListener
	 */
	public void registerForKeyboardEvent() {
		// pass through all our cells
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				// inform them to call me back
				cell[i][j].registerCellKbListener(this);
			}
		}
	}
	/*
	 * When the Grid register itself as a SudoduCellKbListener to the cells
	 * the cell will call back this method with the key pressed
	 */
	public void keyPressed(Cell cell, int x, int y, KeyEvent e) {
		// test first for cursor movement
		int code = e.getKeyCode();
		switch(code) {
		    // check for cursor movement or keybad or tab
			case KeyEvent.VK_LEFT:
			case KeyEvent.VK_RIGHT:
			case KeyEvent.VK_UP:
			case KeyEvent.VK_DOWN:
			case KeyEvent.VK_KP_LEFT:
			case KeyEvent.VK_KP_RIGHT:
			case KeyEvent.VK_KP_UP:
			case KeyEvent.VK_KP_DOWN:
			case KeyEvent.VK_TAB:
				changeFocus(code, x, y);
				return;
			default:
				break;
		}
		
		// if the cell is an original problem cell we cannot change it
		if(cell.isOriginalProblem())
			return;
		// other checks if it is not a digit or a character exit
		char c = Character.toLowerCase(e.getKeyChar());
		// get the value from conversion at base 36 which is the largest
		try {
			int value = Integer.parseInt("" + c, Character.MAX_RADIX);
			// if >= the size of our grid, ignore it
			if(value >= size)
				return;
			// so set the value of the cell received as parameter to that value
			// if it is legal
			if(isAvailable(x, y, value)) {
				cell.setValue(value);
				// pass to next cell so set the value of code to right cursor
				changeFocus(KeyEvent.VK_RIGHT, x, y);
			}
		}
		catch(Exception ex) {
			return;					// just ignore it
		}
	}
	
	/*
	 * Use to perform change of Cell depending of the keyTyped
	 * when cursor movement
	 */
	private void changeFocus(int code, int x, int y) {
		// direction where I will move
		switch(code) {
		    // check for cursor movement or keybad or tab
			case KeyEvent.VK_LEFT:
			case KeyEvent.VK_KP_LEFT:
				y--;
				break;
			case KeyEvent.VK_RIGHT:
			case KeyEvent.VK_KP_RIGHT:
			case KeyEvent.VK_TAB:
				y++;
				break;
			case KeyEvent.VK_UP:
			case KeyEvent.VK_KP_UP:
				x--;
				break;
			case KeyEvent.VK_DOWN:
			case KeyEvent.VK_KP_DOWN:
				x++;
				break;
			default:
				return;
		}
		// ok check for wrap around
		// if we went to musch to left
		if(x < 0)
			x = size - 1;
		if(x >= size)
			x = 0;
		if(y < 0)
			y = size - 1;
		if(y >= size)
			y = 0;
		// give the focus to the adjacent cell
		cell[x][y].requestFocus();
	}
	/*
	 * To unit test the whole thing
	 */
	public static void main(String[] args) {
		int size = 9;
		Grid g = new Grid(size);
		// displaying all the cell uniqueId created for debug purposes
		System.out.println("The whole grid");
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				System.out.print(" " + g.cell[i][j].getIdStr());
			}
			System.out.println();
		}
		// the rows
		System.out.println("The " + size + " rows");
		for(int i = 0; i < size; i++)
			System.out.println("Row " + i + ": " + g.row[i]);
		// the columns
		System.out.println("The " + size + " columns");
		for(int i = 0; i < size; i++)
			System.out.println("Col " + i + ": " + g.column[i]);
		// the regions
		System.out.println("The " + size + " regions");
		for(int i = 0; i < size; i++)
			System.out.println("Region " + i + ": " + g.region[i]);
		// test the get region method, for column and row it is quite evident
		// but for region we have to test
		RowColReg rcr = g.getRegion(7, 7);
		System.out.println("Region where [7,7] resides : " + rcr);
		rcr = g.getRegion(1, 1);
		System.out.println("Region where [1,1] resides : " + rcr);

	}

}


In the next turorial we will introduce a BruteForce solving algorithm and some intersting problems.

This post has been edited by pbl: 20 October 2010 - 08:29 PM


Is This A Good Question/Topic? 3
  • +

Page 1 of 1