Page 1 of 1

Sudoku VI - Grid generator How to generate a grid with the previous posted classes Rate Topic: -----

#1 pbl  Icon User is offline

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

Reputation: 8328
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Posted 21 October 2010 - 10:15 PM

Now we will generate randomly a Sudoku grid.

One new class will have to be added. Two of the previously posted classes will need modifications.
These updated new classes are posted in this tutorial as the new one.

As usual, the Sudoku generator class can be used in both console and a GUI mode.

How to generate a Sudoku grid ?
Use a an empty grid and then to randomly add cell values if these values are available.

There are a lot of comments in the code which use previoulsly posted class source code.

Two previously posted classes needed modifications.
- the Grid class that required modification to return the grid size. Curiously, this information was not required anywhere in the code before
- the GridGuiOne class needs now to be able to return the Grid object it was built from. This was the easiest way to implement the new SudokuGenerator class to support console and GUI operation. If its constructor is called with a Grid object as parameter, it will work in console mode, if it is called with a GridGuiOne object as parameter it will work in Swing mode with a Swing timer

A new class has been added the SudokuGenerator class. It contains a main() method that first build a new Sudoku grid and then build one using the GUI interface to display the built in progress.

The next tutorial will be on how, from a complete grid, put blank cells and still make the grid valid (aka still having a single unique solution)

The new class SudokuGenerator.java

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

import javax.swing.*;

/*
 * This class is used to generate a Sudoku grid
 * It's main() method is there to test both in console mode both in GUI mode
 * the whole process
 */
public class SudokuGenerator implements ActionListener {

	// The Grid that will be generated
	private Grid grid;
	// If Gui mode or not
	private boolean useGui;
	// the Grid cells 
	private int size;
	// an arrayList to pickup cells to fill
	private ArrayList<Point> al;
	// the random generator
	private Random ran;
	// the Swing timer for GUI mode
	private javax.swing.Timer timer;
	// a counter if we get stuck
	private int stuckCounter;
	// how much we will fall back when stuck
	private int fallBack;
	// number of iteration performed
	private int nbIter;
	// where we are
	private int cellId;
	
	/*
	 * Constructor with or without GUI
	 */
	public SudokuGenerator(Grid grid) {
		this.grid = grid;
		useGui = false;
		init();
	}
	public SudokuGenerator(GridGuiOne gridPanel) {
		grid = gridPanel.getGrid();
		useGui = true;
		init();
	}
	private void init() {
		// save size
		size = grid.getSize();
		// create the arrayList
		al = new ArrayList<Point>();
		// fill it with the cell to process
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				al.add(new Point(i,j));
			}
		}
		ran = new Random();
	}
	/*
	 * Getter to return a new the Grid
	 */
	public void resetGrid() {
		// clear the Grid
		grid.clearCell();
		// cell to process
		cellId = 0;
		// set to 0 our stuck counter
		stuckCounter = 0;
		fallBack = 5;
		nbIter = 0;
		// start the process depending if GUI or not
		if(useGui) {
			timer = new javax.swing.Timer(250, this);
			timer.start();
		}
		else {				// console mode
			resetConsole();
		}
	}
	
	/*
	 * reset in console mode
	 * we just loop until the ArrayList is empty
	 */
	private void resetConsole() {
		// loop until all done
		while(cellId != size * size) {
			// ok try to put a value in a cell
			testNextOne();
		}
	}
	/*
	 * The method called by the Swing timer
	 */
	@Override
	public void actionPerformed(ActionEvent e) {
		// test if we are done
		if(cellId == size * size) 
			timer.stop();
		else
			testNextOne();
	}
	
	/*
	 * Will try to find a value for a cell
	 */
	private void testNextOne() {
		// if the number of iteration id to big we are really not on a good path
		// so reset the whole thing
		if(nbIter > size * size * 3) {
			// put all the cells back to 0
			for(int i = 0; i < cellId; i++) {
				Point p = al.get(i);
				grid.setCellValue(p.x, p.y, 0);
			}
			// reset number of iteration and other counters
			nbIter = 0;
			stuckCounter = 0;
			fallBack = 5;
		}
		// number of iteration done
		++nbIter;
		// test if we seem stuck
		if(stuckCounter > 5) {
			for(int i = 0; i < fallBack; i++) {
				Point p = al.get(cellId--);
				grid.setCellValue(p.x, p.y, 0);
			}
			// reset stuck counter and increment fall back for next time
			stuckCounter = 0;
			++fallBack;
			// but not too much
			if(fallBack > 10)
				fallBack = 5;
		}
		// select randomly a cell to fill
		Point p = al.get(cellId);
	    // get the possible values for that cell
		int[] val = grid.getAllAvailableValues(p.x, p.y);
		// if no available value
		if(val.length == 0) {
			// put back go back
			--cellId;
			// set its value to precceding one to zero
			Point previous = al.get(cellId);
			grid.setCellValue(previous.x, previous.y, 0);
			// increment our stuck counter
			++stuckCounter;
			// we will try to fix at next call
			return;
		}
		// ok we will try to put a value
		grid.setCellValue(p.x, p.y, val[ran.nextInt(val.length)]);
		// validate that by doing that we wont get stuck
		for(int i = cellId + 1; i < size * size; i++) {
			Point tp = al.get(i);
			val = grid.getAllAvailableValues(tp.x, tp.y);
			// oups if 0 for one cell not a good ides
			if(val.length == 0) {
				// put the original cell back in the cell to process
				grid.setCellValue(p.x, p.y, 0);
				// fall back two cells before to cancel the cellId++ after the loop
				cellId -= 2;
				++stuckCounter;
				break;					// no need to continue
			}
		}
		// process we next cell, if it failed 
		cellId++;
	}
	
	/*
	 * To unit test the whole thing
	 */
	public static void main(String[] args) {
		// create a Grid
		Grid grid = new Grid(16);
		// create a Sudoku generator for that object in console mode
		SudokuGenerator sg = new SudokuGenerator(grid);
		// reset the grid
		sg.resetGrid();
		// print it
		grid.printGrid();
		
		// now make a GUI version
		grid = new Grid(9);
		// build a Panel for it
		GridGuiOne panel = new GridGuiOne(grid);
		// create a JFrame to display it
		JFrame frame = new JFrame("Sudoku generator");
		frame.add(panel);
		frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
		frame.setVisible(true);
		frame.pack();
		// the packed frame will only be good to display "" blank labels when
		// number will pe put it wont resize so we will have to make it a little bit bigger
		Dimension d = frame.getSize();
		d.height *= 7;
		d.width *= 7;
		d.height /= 6;
		d.width /= 6;
		frame.setSize(d);
		// create a SudukuGenerator GUI mode
		sg = new SudokuGenerator(panel);
		sg.resetGrid();
		try {
		Thread.sleep(1000);
		}
		catch(Exception e) {}
		
	}
}





The modified GidGuiOne.java that now returns the Grid object from which it was built

import javax.swing.*;
import java.awt.*;
/*
 * A Basic JPanel to display the cells
 */
public class GridGuiOne extends JPanel {

	private static final long serialVersionUID = 1L;

	// grid saved 
	private Grid grid;
	
	// Constructor receives an instance of class Grid as parameter
	GridGuiOne(Grid grid) {
		this.grid = grid;
		// get the regions from the Grid
		RowColReg[] region = grid.getRegion();
		// get the size to get the number of row and column in each region
		// and the total of regions per row/column
		int size = (int) Math.sqrt((double) region.length);
		
		// this (the main panel) will contain size X size regions
		setLayout(new GridLayout(size, size));
		// now we will build the other panels (one for each region)
		for(int i = 0; i < region.length; i++) {
			JPanel p = new JPanel(new GridLayout(size, size));
			p.setBorder(BorderFactory.createLineBorder(Color.BLACK));
			// get the cells from that region
			Cell[] cell = region[i].getCells();
			// add the cell to the grid
			for(int j = 0; j < cell.length; j++) {
				p.add(cell[j]);
			}
			// then add this panel of a region to the big grid
			add(p);
		}
	}
	
	/*
	 * Used by the SudokuGenerator to get the Grid in GUI mode
	 */
	public Grid getGrid() {
		return grid;
	}
	/*
	 * To test the Grid
	 */
	public static void main(String[] atgs) {
		// create a JFrame to hold the Grid
		JFrame frame = new JFrame("First GUI demo");
		frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
		// Build a Grid of size 9
		Grid grid = new Grid(9);
		// load the grid with predefined problem
		Problems.setProblem3(grid);
		// ask the Grid to react to keyboard event
		grid.registerForKeyboardEvent();
		// build a GridGuiOne from that Grid object
		GridGuiOne ggo = new GridGuiOne(grid);
		// add the Grid to the Frame
		frame.add(ggo);
		// make it visible
		frame.setVisible(true);
		frame.pack();
	}
}




The Grid.java class that can now return the size of the grid


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++;
			}
		}
	}

	/*
	 * Constructor to clone a Grid
	 */
	public Grid(Grid g) {
		// call back my original constructor 
		this(g.size);
		// set the cells values
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				// get original cell value
				int value = g.getValue(i, j);
				// if value == 0 no need to process constructor alread init it to 0
				if(value > 0) {
					// call setter depending if originalProblem or not
					if(g.isOriginalProblem(i, j))
						setOriginalProblemValue(i, j, value);
					else
						setCellValue(i, j, value);
				}
			}
		}
	}
	/*
	 * 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]];
	}
	// return the size of the Grid required by the SudokuGenerator
	public int getSize() {
		return cell.length;
	}
	// returns the cells for the GUIs that want to put their own Listener on them
	public Cell[][] getCells() {
		return cell;
	}
	// clear all the cells when we want to create a new grid
	public void clearCell() {
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				cell[i][j].setValue(0);
			}
		}
	}

	/*
	 * 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();
	}
	
	/*
	 * Test if 2 Grid are equals
	 */
	public boolean equals(Grid g) {
		// test the size first
		if(size != g.size)
			return false;
		// compare all cells
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				// if any cell not equal return false
				if(!(cell[i][j].equals(g.cell[i][j])))
					return false;
			}
		}
		return true;
	}
	/*
	 * 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);
	}

}




Enjoy

This post has been edited by pbl: 22 October 2010 - 06:41 PM


Is This A Good Question/Topic? 1
  • +

Page 1 of 1