Constraint Processing

Aus ProgrammingWiki

Archivierte Version vom 2013-06-13T14:39:44+00:00. Aktuelle Version

Inhaltsverzeichnis

1 CP solver for the Sudoku game

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.

-->

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

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

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

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

Constraint Processing

Inhaltsverzeichnis

CP solver for the Sudoku game

Introduction

Modeling Sudoku as Constraint Satisfaction Problem

Solving Sudoku with the basic Backtracking Solver

Suche