Page 1 of 1

Sudoku II - the Brute Force Solving a Sudoku problem Rate Topic: ****- 1 Votes

#1 pbl  Icon User is offline

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

Reputation: 8334
  • View blog
  • Posts: 31,858
  • Joined: 06-March 08

Posted 19 October 2010 - 09:48 PM

For solving a Sudoku problem you can use the brute force algorithm

As described in Wikipedia

http://en.wikipedia....hmics_of_sudoku

the BruteForce algorithm consist of

Briefly, a brute force program would solve a puzzle by placing the digit "1" in the first cell and checking if it is allowed to be there. If there are no violations (checking row, column, and box constraints) then the algorithm advances to the next cell, and places a "1" in that cell. When checking for violations, it is discovered that the "1" is not allowed, so the value is advanced to a "2". If a cell is discovered where none of the 9 digits is allowed, then the algorithm leaves that cell blank and moves back to the previous cell. The value in that cell is then incremented by one. The algorithm is repeated until the allowed value in the 81st cell is discovered. The construction of 81 numbers is parsed to form the 9 x 9 solution matrix.

In this turorial we will show how an optimized Brute Force algorithm can work

You will need the classes posted in Sudoku-I to run the following programs.

But first we will introduce a new class Problems.java
this class contains, for the moment, 2 different Sudoku problems. One intermediate one, and one which, according to internet research is a very nice canditate to be a worst case to be solved with the Brute ALgorithm.

This Problems class will probably grow as we will study other problems. It contains static methods to fill your Sudoku Grid with already registered problems. It also contains a main() method for unit tests.

Here is the Problems.java class

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

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




Now the BruteForce class. It has a console mode and a GUI mode. For now jjust use the console mode.
It uses a Grid fill with data and solves using the BruteForce algorithm a Sudoku problem.

Right now it's main methot uses setProblem1() method to load a standard Sudoku problem
Try it with that set up and then, try with the setProble2() method. You will see that it will take much longer to found the solution.

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

}



The next tutorial will introduce 2 GUIs that you will be able to play with.

This post has been edited by pbl: 21 October 2010 - 04:44 PM


Is This A Good Question/Topic? 4
  • +

Replies To: Sudoku II - the Brute Force

#2 rishabhsharma  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 10
  • View blog
  • Posts: 342
  • Joined: 26-March 09

Posted 16 May 2012 - 10:56 AM

Sir where(package) this Grid class resides ...???
Was This Post Helpful? 0
  • +
  • -

#3 Ryano121  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1362
  • View blog
  • Posts: 3,002
  • Joined: 30-January 11

Posted 16 May 2012 - 11:19 AM

Read the first tutorial in this series -

http://www.dreaminco...-i-basic-tools/
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1