Constraint Processing

Wiki-Quelltext dieser Seite.

<language>Java</language>
== CP solver for the Sudoku game ==
=== Introduction ===
Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution.

[[Bild:Sudoku.png|200px]] --> [[Bild:Sudoku2.png|200px]]

=== Modeling Sudoku as Constraint Satisfaction Problem ===

'''Variables:''' $X_{11},...,X_{99}$

'''Domains:''' {1,..,9}

'''Constraints:''' 
* '''Row Constraints''' $X_{11} \neq X_{12},..,X_{11} \neq X_{19}$ etc. 
* '''Column Constraints''' $X_{11} \neq X_{21},..,X{11} \neq X_{91}$ etc.
* '''Block Constraints''' $X_{11} \neq X_{12},..,X_{11} \neq X_{33}$ etc.

We have 81 squares. Each square is part of 20 binary constraints of form $X_i \neq X_j$: 8 row constraints + 8 column constraints + 4 block constraints. So in total there are 81 * 20 / 2 = 810 constraints. 

=== Solving Sudoku with the basic Backtracking Solver ===
<code id="51b9ba2932671">
public Object Variable(){
    int value = -1;
    int row = -1;
    int col = -1;
    int[] domain = new int[]{1,2,3,4,5,6,7,8,9};
    return this;
}
</code>
<code id="51b9d8c9c9860">
public Object Constraint(){
   Object variable_1 = null;
   Object variable_2 = null;

   public void setVariables(Object constraint, Object v1, Object v2){
     constraint.variable_1 = v1;
     constraint.variable_2 = v2;
   }
   
   public boolean check(Object c){
      if(c.variable_1.value != -1 && c.variable_2.value != -1){
        if(c.variable_1.value != c.variable_2.value){
           return true;
        }
        return false;
      }
      return true;
   }
   return this;
}

</code>
<code id="51b9d8c9c9bcd" id="51b9a50c38e1c>
import java.util.List;

public Object Solver(){

	List constraints;

	public void setConstraints(Object solver, List constraints) {
		solver.constraints = constraints;
	}

	public boolean backtrack(Object s, List partial, List pending) {

		if (pending.size() == 0) {
			return true;
		}

		Object next = pending.remove(0);

		for (int i = 0; i <= next.domain.length; i++) {

			next.value = next.domain[i];
			partial.add(next);

			if (check_All(s)) {
				if (backtrack(s, partial, pending)) {
					return true;
				} else {
					partial.remove(next);
					next.value = -1;
				}
			} else {
				partial.remove(next);
				next.value = -1;
			}
		}

		pending.add(0, next);

		return false;
	}

	private boolean check_All(Object s) {
		for (int i = 0; i < s.constraints.size(); i++) {
			Object dc = s.constraints.get(i);
			if (!dc.check(dc)) {
				return false;
			}
		}
		return true;
	}
        
        return this;
}
</code>
<code id="51b9e51c834c1">
List pending = new ArrayList();
List solution = new ArrayList();

Object[][] variables = new Object[9][9];

for(int i=0; i<6; i++){
 for(int j=0; j<6; j++){
  Object v = Variable();
  pending.add(v);
  variables[i][j] = v;
 }
}
</code>
<code id="51b9e51c83556">
List constraints = new ArrayList();

for(int i=0; i<6; i++){
 for(int j=0; j<6; j++){
 
  Object v = variables[i][j];
  for(int k=j+1; k<6; k++){
   
   Object constraint = Constraint();
   Object v_2 = variables[i][k];
   constraint.setVariables(constraint, v, v_2);
   constraints.add(constraint);
  }
 }
}
</code>
<code id="51b9e51c835db">
for(int i=0; i<6; i++){
 for(int j=0; j<6; j++){

  Object v = variables[j][i];
  for(int k=j+1; k<6; k++){
   Object constraint = Constraint();
  
   Object v_2 = variables[k][i];
   
   constraint.setVariables(constraint, v, v_2);
  
   constraints.add(constraint);

  }
 }
}
</code>
<code id="51b9fb5c719dc">
for(int i=0; i<6; i=i+2){
 for(int j=0; j<6; j=j+3){
 
  Object v = variables[i][j];
  Object v_2 = variables[i+1][j+1];
  Object v_3 = variables[i+1][j+2];
   
  Object constraint = Constraint();
  constraint.setVariables(constraint, v, v_2);
  Object constraint2 = Constraint();
  constraint2.setVariables(constraint2, v,v_3);
  
  constraints.add(constraint);
  constraints.add(constraint2);
 }
}
</code>
<code id="51ba14938fad3">
variables[1][2].domain = new int[]{1};
variables[1][5].domain = new int[]{5};
variables[2][1].domain = new int[]{6};
variables[2][5].domain = new int[]{2};
variables[3][0].domain = new int[]{5};
variables[0][4].domain = new int[]{1};
variables[3][4].domain = new int[]{1};
variables[4][4].domain = new int[]{3};
variables[5][2].domain = new int[]{3};
</code>
<run id="51b9b94e8299f">
Object solver = Solver();
solver.setConstraints(solver, constraints);

if(solver.backtrack(solver, solution, pending)){
  
for(int i=0; i<6; i++){
  String line = "";
  for(int j=0; j<6; j++){

   Object va = variables[i][j];
   int val = va.value;
   line = line + val + " ";
  } 
  System.out.println(line);
}
}
</run>