Page 1 of 1

Sudoku V - Validating a grid Using Brute Force 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 21 October 2010 - 06:46 PM

In this turorial we will see how we validate if a Sudoku grid is valid. By valid we mean if a Sudoku grid has a unique solution.

In the previous tutorial about the Brute Force we saw how it was possible to apply an algorithm to solve a Sudoku grid by testing all possibilities.

Furthermore we have seen that depending of the disposition of the numbers in the grid how the efficiency of the Brute Force algorithm can vary. There is a proposed problem that shows this and shows also how solving the problem in reversed order (from row 9 column 9 to row 1 column 1 instead of solving it from row 1 column 1 to row 9 column 9) can drastically change the time it takes to perform the operation.

Now an easy way to test if a Sudoku grid has a unique solution is to:
- apply the Brute Force to the grid
- apply the Brute force in reversed order to the grid

If both solved grids are equals, it means that the Sudoku grid has a unique solution.

To perform these tasks the following class are posted:
- the BruteForce has been modified. It has now a static boolean method isValidSudoku(Grid grid) to perform the check. There is also a method isValidSudoku(Grid grid, boolean printFlag) that receives a flag to display the 3 grids (original one, solved regular, solved in reverse)

To perform the check, we have to make a copy of the grid, so we can apply the algorithm on 2 different grids. After the operation, we have to be able to compare the 2 grids.
- the Grid class has been modified 1) with a new constructor to clone a Grid object 2) with an equals() method to compare 2 Grid objects

- the Problems class has been modified to contain an invalid Sudoku grid to test the whole thing
- the TestIfValidGrid class has been added. It contains a main() method to unit test the whole thing.

The mentionned classes follow. Enjoy

Cell.java

/*
 * 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;
	}
	
	/*
	 * Test if 2 Cells are equals (does not check the position 
	 * neither if originalProblem or not)
	 */
	public boolean equals(Cell c) {
		return value == c.value;
	}
	/*
	 * 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) {}
}



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

	/*
	 * 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]];
	}

	/*
	 * 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);
	}

}



BruteForce.java

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

import javax.swing.Timer;
/*
 * Contains methods to solve by brute force a Sudoku Grid
 * It implements an ActionListener for whn run in GUI mode
 */
public class BruteForce implements ActionListener {

	// the Grid I will have to work on
	private Grid grid;
	// the ArrayList containing the cells that have to be fixed
	private ArrayList<Point> al;
	// the number of cells to fix (the ArrayList size)
	private int nbTodo;
	// the index we are at
	private int index;
	// the SwingTimer use when do in GUI mode
	private Timer timer;
	
	/*
	 * Constructor
	 */
	public BruteForce(Grid grid) {
		this.grid = grid;
	}
	
	/*
	 * To solve the Grid in console mode will throw an exception if the problem is not feasible
	 */
	public void solve() {
		solve(false);			// call ny default no reverse
	}
	// With the reverse flag
	public void solve(boolean reverse) {
		// The ArrayList of cells to fill
		al = grid.getCellsToFill();
		// get it's size once
		nbTodo = al.size();
		// if nothing to do
		if(nbTodo == 0) 
			return;
		// if as to be reversed call the method doing it
		if(reverse)
			al = reverse(al);
		// index we will search
		index = 0;
		// for the console method we just loop until we are done
		while(index < nbTodo) {
			// common method
			performFill();
		}
		return;
	}
	/*
	 * To solve the Grid with GUI will throw an exception if the problem is not feasible
	 */
	public void solveWithGui(boolean reverse) {
		// The ArrayList of cells to fill
		al = grid.getCellsToFill();
		// get it's size once
		nbTodo = al.size();
		// if nothing to do
		if(nbTodo == 0) 
			return;
		// if as to be reversed call the method doing it
		if(reverse)
			al = reverse(al);
		// index we will search
		index = 0;
		// create the Timer that will be invoked 10 times a second
		timer = new Timer(100, this);
		timer.start();
		return;
	}
	/*
	 * The common method used by both the Console mode and the GUI mode
	 * The console mode method solve() just call it in a while
	 * the GUI mode calls it through a SwingTimer
	 */
	private void performFill() {
		// process next cell if index = -1 it means the solution is not feasible
		// it is in invalid Sudoku problem (you havent fill the cells with the GUI)
		if(index < 0)
			throw new IllegalStateException("Trying to solve an invalid Sudoku problem");
		Point p = al.get(index);
		// get its possible values
		int[] guess = grid.getAllAvailableValues(p.x, p.y);
		// if no possible values fall back to previous cell at next call
		if(guess.length == 0) {
			--index;				// use previous one
			return;
		}
		// get its value (will be 0 at first trial)
		int value = grid.getValue(p);
		// if it is first trial use the first one in the array
		if(value == 0) {
			grid.setCellValue(p.x, p.y, guess[0]);
			++index;				// go check next one at next call
			return;
		}
		// test if the value used is the last of the list
		if(value == guess[guess.length - 1]) {
			// reset this cell value to 0 to start all the process again
			grid.setCellValue(p.x, p.y, 0);
			// and go back to the previous one
			--index;
			return;
		}
		// OK we will have to try the next available one
		for(int lastUsed = 0; lastUsed < guess.length; ++lastUsed) {
		   // when we found the last one we have tried
		   if(value == guess[lastUsed]) {
			   // use  +1 to check the next one
			   grid.setCellValue(p.x, p.y, guess[lastUsed+1]);
			   ++index;
			   break;   // no need to continue the loop
		   }
		}	
	}

	/*
	 * Called by the SwingTimer when in GUI mode to update
	 * the search and the GUI
	 */
	@Override
	public void actionPerformed(ActionEvent e) {
		// if we are done
		if(index == nbTodo) {
			timer.stop();
			return;
		}
		// not done we have to update one batch
		performFill();
	}

	/*
	 * Reverse and ArrayList of Point to test the solution in reverse 
	 * this is used to find if the the solution is unique
	 */
	private ArrayList<Point> reverse(ArrayList<Point> order) {
		// create new ArrayList
		ArrayList<Point> al = new ArrayList<Point>();
		int size = order.size();
		// loop in reverse
		for(int i = size-1; i >= 0; i--)
			al.add(order.get(i));
		// return it
		return al;
	}
	
	/* 
	 * A static method to test if a Sudoku grid is a valid Sudoku grid
	 * To perform this test we apply the normal brute force and the
	 * reversed but force to the Grid. 
	 * If the 2 solved problems are the same we can conclude that there
	 * is only one solution
	 * A print flag is used if you want to print the 2 solved grid
	 */
	public static boolean isValidSudoku(Grid origGrid) {
	   return isValidSudoku(origGrid, false);
	}
	public static boolean isValidSudoku(Grid origGrid, boolean printFlag) {
		// build two copies of the original Grid because the 
		// BruteForce process fills the grid to find the solution
		Grid[] grid = new Grid[2];
		boolean[] reverseFlag = {false, true};
		// build the 2 solutions
		for(int i = 0; i < 2; i++) {
			// build a copy of the Grid
			grid[i] = new Grid(origGrid);
			// create a BruteForce object out of that grid
			BruteForce bf = new BruteForce(grid[i]);
			// call the solving method one reverse one not
			bf.solve(reverseFlag[i]);
		}
		// if printFlag is on we print the grids
		if(printFlag) {
			System.out.println("The original Grid");
			origGrid.printGrid();
			System.out.println("The solved Grid");
			grid[0].printGrid();
			System.out.println("The solved Grid in reverse");
			grid[1].printGrid();
		}
		// return if the 2 grids are the same
		return grid[0].equals(grid[1]);
	}
	/*
	 * To Unit test the whole thing
	 */
	public static void main(String[] args) {
		// Build a Grid
		Grid grid = new Grid(9);
		// load it with one of our prepared model
		Problems.setProblem1(grid);
		
		grid.printGrid();
		
		BruteForce bf = new BruteForce(grid);
		bf.solve(false);
		grid.printGrid();
	}

}




Problems.java

/**
 * A class that contains, for test purpose, the setters for different
 * Sudoku problems
 */
public class Problems {

	/*
	 * private method called by the others to load a problem
	 */
	private static void load(Grid grid, int[][] val) {
		// clear grid because if it already contains something
		// the setOriginalProblemValue might reject to set a cell to a value already there
		for(int i = 0; i < val.length; i++) {
			for(int j = 0; j < val[i].length; j++) {
				grid.setCellValue(i, j, 0);	
			}
		}
		// load with new problem
		for(int i = 0; i < val.length; i++) {
			for(int j = 0; j < val[i].length; j++) {
				grid.setOriginalProblemValue(i, j, val[i][j]);	
			}
		}
	}
	// preregistered problem 1	
	public static void setProblem1(Grid grid) {
		int[][] val = {
				{0, 0, 0, 0, 0, 7, 0, 0, 0},
				{3, 0, 0, 0, 6, 0, 0, 5, 0},
				{7, 0, 0, 9, 2, 0, 0, 1, 0},
				{0, 8, 0, 0, 3, 0, 0, 0, 1},
				{0, 0, 0, 0, 0, 0, 5, 0, 6},
				{9, 0, 0, 6, 0, 8, 0, 0, 0},
				{0, 0, 0, 0, 1, 3, 6, 0, 0},
				{0, 0, 0, 5, 0, 0, 1, 2, 0},
				{0, 9, 0, 0, 0, 0, 7, 0, 3}
		};
		// loat it with my values
		load(grid, val);
	}

	/*
	 * preregisterd problem 2
	 * this is kind of worst case for brute force
	 * no clue on top row where the only solution is 987654321 
	 * so a huge amount of iterations will be required
	 * this a good problem to test in the brute force with reverse in BruteForceGui.java
	 * (may be not with the GUI version it would take a while :-))
	 */
	public static void setProblem2(Grid grid) {
		int[][] val = {
				{0, 0, 0, 0, 0, 0, 0, 0, 0},
				{0, 0, 0, 0, 0, 3, 0, 8, 5},
				{0, 0, 1, 0, 2, 0, 0, 0, 0},
				{0, 0, 0, 5, 0, 7, 0, 0, 0},
				{0, 0, 4, 0, 0, 0, 1, 0, 0},
				{0, 9, 0, 0, 0, 0, 0, 0, 0},
				{5, 0, 0, 0, 0, 0, 0, 7, 3},
				{0, 0, 2, 0, 1, 0, 0, 0, 0},
				{0, 0, 0, 4, 0, 0, 0, 0, 9}
		};
		// loat it with my values
		load(grid, val);
	}
	
	/*
	 * and almost done Sudoku problem to see the BruteForce GUI in action
	 * the top part if almost done so the reversed method should be slower 
	 * on that one
	 */
	public static void setProblem3(Grid grid) {
		int[][] val = {
				{6, 1, 9, 2, 8, 4, 5, 7, 3},
				{3, 7, 0, 5, 1, 6, 4, 0, 9},
				{4, 5, 2, 0, 7, 0, 8, 0, 0},
				{7, 4, 5, 9, 0, 3, 1, 0, 0},
				{2, 0, 0, 8, 5, 1, 7, 9, 0},
				{8, 9, 1, 0, 2, 0, 3, 6, 0},
				{5, 0, 0, 6, 3, 0, 9, 0, 1},
				{0, 0, 3, 0, 0, 2, 6, 0, 7},
				{1, 0, 4, 0, 9, 0, 0, 0, 0}
		};
		// loat it with my values
		load(grid, val);
	}

	/*
	 * And invalid Sudoku (more than one solution)
	 * to test the static method in BruteForce that check if a sudoku is valid
	 * The row #4 with makes the Sudoku problem valid has been commented out
	 * removing the 5 in the last column makes this Sudoku a non valid
	 * Sudoku problem
	 */
	public static void setValidProblem1(Grid grid) {
		int[][] val = {
				{6, 0, 0, 0, 0, 0, 1, 4, 0},
				{3, 0, 8, 0, 0, 4, 0, 0, 6},
				{0, 0, 0, 0, 0, 0, 0, 0, 0},
				{0, 0, 0, 2, 0, 0, 0, 0, 5},  // <--- requires the 5 here to be valid
				{0, 2, 1, 0, 3, 6, 0, 0, 4},
				{0, 0, 0, 0, 0, 0, 7, 0, 0},
				{0, 0, 7, 0, 5, 0, 3, 9, 1},
				{5, 0, 6, 0, 0, 1, 0, 0, 7},
				{0, 9, 0, 7, 4, 2, 0, 0, 0}
		};
		// loat it with my values
		load(grid, val);		
	}
	public static void setInvalidProblem1(Grid grid) {
		int[][] val = {
				{6, 0, 0, 0, 0, 0, 1, 4, 0},
				{3, 0, 8, 0, 0, 4, 0, 0, 6},
				{0, 0, 0, 0, 0, 0, 0, 0, 0},
				{0, 0, 0, 2, 0, 0, 0, 0, 0},  // <--- invalid with this row 
// valid row	{0, 0, 0, 2, 0, 0, 0, 0, 5},  // <--- requires the 5 here to be valid
				{0, 2, 1, 0, 3, 6, 0, 0, 4},
				{0, 0, 0, 0, 0, 0, 7, 0, 0},
				{0, 0, 7, 0, 5, 0, 3, 9, 1},
				{5, 0, 6, 0, 0, 1, 0, 0, 7},
				{0, 9, 0, 7, 4, 2, 0, 0, 0}
		};
		// loat it with my values
		load(grid, val);		
	}
	/*
	 * To unit test the whole thing
	 */
	public static void main(String[] args) {
		// create a Grid
		Grid grid = new Grid(9);
		// fill and print it
		setProblem1(grid);
		grid.printGrid();
		// fill and print it
		setProblem2(grid);
		grid.printGrid();
		// fill and print it
		setProblem3(grid);
		grid.printGrid();
	}
}




TestIfValidGrid.java

/*
 * A simple class that holds a main() method to unit test the 
 * the method in BruteForce that test if a Sudoku grid is valid
 */
public class TestIfValidGrid {

	/*
	 * The main() method
	 */
	public static void main(String[] args) {
		// Build the Grid
		Grid grid = new Grid(9);
		
		// Load it with an valid problem
		System.out.println("Test with a valid problem");
		Problems.setValidProblem1(grid);
		// call the method that validates asking it to display the grids
		boolean status = BruteForce.isValidSudoku(grid, true);
		System.out.println("Methods returns equals: " + status);
        System.out.println();
        
		// Load it with an invalid problem
		System.out.println("Test with an invalid problem");
		Problems.setInvalidProblem1(grid);
		// call the method that validates asking it to display the grids
		status = BruteForce.isValidSudoku(grid, true);
		System.out.println("Methods returns equals: " + status);
	}
}




Is This A Good Question/Topic? 0
  • +

Page 1 of 1