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(Variable v1, Variable v2){
     this.variable_1 = v1;
     this.variable_2 = v2;
   }
   
   public boolean check(){
      if(variable_1.value != -1 && variable_2.value != -1){
        if(variable_1.value != variable_2.value){
           return true;
        }
        return false;
      }
      return true;
   }
   return this;
}

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

public class Solver {

	List constraints;

	public void setConstraints(List constraints) {
		this.constraints = constraints;
	}

	public boolean backtrack(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()) {
				if (backtrack(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() {
		for (int i = 0; i < this.constraints.size(); i++) {
			Object dc = this.constraints.get(i);
			if (!dc.check()) {
				return false;
			}
		}
		return true;
	}
        
        return this;
}
</code>
<run id="51b9b94e8299f"></run>