Versionsvergleich
Aus ProgrammingWiki
Vergleich: 2013-06-13T18:02:32+00:00 → 2013-06-21T07:34:24+00:00
<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. |
| + | In out lecture you already learned about a generic backtracking algorithm that is able to solve any Constraint Satisfaction Problem (CSP) with ''variables'', ''domains'' and ''constraints''. In order to reduce the search space, we used forward checking and arc consistency methods. These algorithms remove inconsistent values from the domains of the variables, that are not yet part of the partial solution. They work for ''binary constraints'' as well as for ''non-binary constraints''. For the latter, just recapitulate one possible ''generic arc consistency algorithm'': |
| − | [[Bild:Sudoku.png|200px]] --> [[Bild:Sudoku2.png|200px]] |
| + | '''procedure GAC(G)''' |
| + | Let Q be the set of (undirected) constraints of G |
| + | '''while Q not empty do''' |
| + | select and remove any constraint c from Q; |
| + | '''for each variable x participating in c''' |
| + | REVISE(x,c) |
| + | '''if REVISE(x,c) changed the domain of x then''' |
| + | add to Q the set of all constraints that include x (except c); |
| − | === Modeling Sudoku as Constraint Satisfaction Problem === |
| + | The REVISE procedure can be described as follows: |
| − | '''Variables:''' $X_{11},...,X_{99}$ |
| + | '''procedure REVISE (x,c)''' |
| + | '''for each value a in domain of x do''' |
| + | '''if there is no tuple in the relation of c that includes (x,a) and is valid''' |
| + | then delete a from the domain of x |
| − | '''Domains:''' {1,..,9} |
| + | We could reuse this algorithm to check any constraint c that comes to our mind. Although this always works, it can be very ineffective. For example, consider a constraint ''alldifferent($x_1,..,x_n$)'' with n variables each having a domain of size d. Then the GAC algorithm runs in $O(n*d^n)$ (for each variable we have to check $d^n$ tuples). It is possible to design specialized algorithms that perform faster. |
| − | '''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. |
| + | Of course, we want to remove exactly those inconsistent values the REVISE-procedure is looking for. However, it is often better not to take the procedure literally! Instead we want to write constraint-specific filtering methods, that exploit the ''semantics of a constraint''. |
| − | 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. |
| + | What I mean is, each constraint should be responsible for maintaining a consistent state of the domains of the variables in its scope. Each constraint should be associated with a specific procedure, that efficiently removes values from the domains that are not part of a valid tuple in the relation. We call this procedure ''propagator''. Our constraint solver doesn't need to know more about a constraint than its propagator method. We say: ''The propagator implements a constraint''. |
| − | === 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; |
| + | === Scheduling of propagators === |
| + | Now let us replace the GAC algorithm by an algorithm that schedules a set of propagators: |
| + | |
| + | '''procedure PROPAGATE''' |
| + | Let Q be the set of constraints of G |
| + | '''while Q not empty do''' |
| + | select and remove any constraint c from Q; |
| + | get propagator p of for c; |
| + | '''p.propagate();''' |
| − | 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; |
| − | } |
| + | But what happens if a propagator changed the domain of a variable x? We know that in this case all constraints that have x in its scope have to be put into Q again. You can decide to make Q, the constraint store, globally accessbile. Then each variable, that notices a change in its domain, can put the corresponding constraints into Q itself. |
| − | </code> |
| − | <code id="51b9d8c9c9bcd" id="51b9a50c38e1c> |
| − | import java.util.List; |
| + | This strategy also helps us to ''maintain'' the consistency during the backtracking search. Depending on the branching strategy, after each branching step the domain of a variable is narrowed to one assignment or to a reduced value set. The variable, whose domain has been changed, updates the constraint store and triggers the propagation. |
| − | public Object Solver(){ |
| + | === Implementing propagators === |
| + | Now you can start to implement your own propagators. Let's start with some examples: |
| − | List constraints; |
| + | ====Propagator for $x<y$==== |
| + | <code id="51c35cd9c9a69"> |
| + | public void prop_inequality(List dx, List dy){ |
| − | public void setConstraints(Object solver, List constraints) { |
| − | solver.constraints = constraints; |
| − | } |
| + | List copy_dx = new ArrayList(dx); |
| + | List copy_dy = new ArrayList(dy); |
| − | public boolean backtrack(Object s, List partial, List pending) { |
| + | int max_y = Collections.max(dy); |
| + | int min_x = Collections.min(dx); |
| − | if (pending.size() == 0) { |
| − | return true; |
| − | } |
| + | for(int i=0; i<copy_dx.size(); i++){ |
| + | int vx = (int) copy_dx.get(i); |
| + | |
| + | if(vx > max_y){ |
| + | dx.remove(vx); |
| + | } |
| + | } |
| − | 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; |
| + | for(int i=0; i<copy_dy.size(); i++){ |
| + | int vy = (int) copy_dy.get(i); |
| + | |
| + | if(vy < min_x){ |
| + | dy.remove(vx); |
| + | } |
| + | } |
} | |
</code> | |
| − | <code id="51b9e51c834c1"> |
| − | List pending = new ArrayList(); |
| − | List solution = new ArrayList(); |
| + | <run id="51c35cd9c9aff"> |
| + | int[] dx = new int[]{2,3,4,5,6}; |
| + | int[] dy = new int[]{1,2,3,4}; |
| − | Object[][] variables = new Object[9][9]; |
| + | List dx_list = Arrays.asList(dx); |
| + | List dy_list = Arrays.asList(dy); |
| − | 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(); |
| + | prop_inequality(dx_list, dy_list); |
| − | 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); |
| − | } |
| − | } |
| + | System.out.println("Domäne von x: "); |
| + | for(int i=0; i< dx_list.size(); i++){ |
| + | System.out.print(dx_list.get(i)); |
} | |
| − | </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); |
| − | |
| − | } |
| − | } |
| + | System.out.println("Domäne von y: "); |
| + | for(int i=0; i< dy_list.size(); i++){ |
| + | System.out.print(dy_list.get(i)); |
} | |
| − | </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> |
| − | <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> |