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
MultiQuote
| 