[PDF] Kakuro comme problème de contrainte

View - Download Kakuro comme problème de contrainte

Previous PDF

Next PDF

Kakuro as a Constraint Problem

Helmut Simonis

4C, Cork Constraint Computation Centre

Department of Computer Science

University College Cork

Ireland

h.simonis@4c.ucc.ie Abstract.In this paper we describe models of the logic puzzle Kakuro as a constraint problem with finite domain variables. We showa basic model expressing the constraints of the problem and presentvarious im- provements to enhance the constraint propagation, and compare alterna- tives using MILP and SAT solvers. Results for different puzzle collections are given. We also propose a grading scheme predicting the difficulty of a puzzle for a human and show how problems can be tightened by removing hints.

1 Introduction

Kakuro is one the many logical puzzles popularized by the Japanese company Nikoli [27]. Table 1 shows a small scale example taken from [26] and its solution. ????23??30??????27??12??16 ??16????2417 ??17??2915 ??35??12?? ????7??87??7 ????11??1610 ??21??5 ??6????3 ????23??30??????27??12??16 ??1697????2417879 ??1789??29158957 ??3568597??12?? ????761??8726??7 ????11??161046132 ??218931??514 ??6312????321

Table 1.Example Problem and Solution

The puzzle is described by the following rules:

1. The puzzle uses a rectilinear grid of black and white cells. Black cells may

contain hints (integer numbers). The number below the diagonal divider is the hint for cells below, the number above the diagonal divider is the hint for cells to the right.

2. The task is to enter numbers from 1 to 9 into the white cells satisfying the

following constraints:(a) The sum of a continuous block of white cell in horizontal (or vertical) direction must be equal to the hint given in the black cell to the left (above). (b) All numbers in a continuous block of white cells must be pairwise differ- ent. The grid size of the puzzle can vary, the largest instance in our evaluation has

124 rows and 90 columns. AvalidKakuro puzzle has solutions, awell posed

problem admits a single solution. An interesting feature oflogical puzzles is that the solution should be deduced with a finite set of deduction rules, without using search. A characterisation of the difficulty of a puzzleinstance is the rule set required to solve it. We show in this paper that all instances from commercial sources used in the tests can be solved by constraint propagation with a generalized arc consistent (GAC) version of thealldifferent-sumconstraint, which combines rules 2a and

2b of the problem description for a set of variables and a simple redundant

constraint modelling the interaction of row and column constraint pairs. We see that a naive model usingalldifferentandsumconstraints is not sufficient, and see how the full constraint propagation can be achieved withoutwriting a specific new global constraint. The constraint programming approach closely resembles the way most humans solve the puzzle by hand. We also present (naive) models using MILP (mixed integer linear program- ming) and a PseudoBoolean model mapped to a SAT solver, whichshow that even for relatively small problem sizes the problem is not trivial.

2 Related Work

Kakuro has become widely popular in the wake of the Sudoku craze that swept country after country in recent years[26]. While the problems are related, their models show significant differences. While Sudoku is mainly concerned with the propagation of thealldifferentconstraint and the interaction of multiple such constraints [18,9,13,7,1], we find that the challenge for Kakuro is the interaction of analldifferentconstraint with thesumconstraint over the same variables. The alldifferent-sumconstraint is not found in the global constraint catalog [2], but a more general constraintweighted-partial-alldiffcould be used. The PhD thesis of S. Thiel [20] describes GAC propagation for part of this constraint. Implementing this global constraint in ECLiPSe for the sole purpose of this analysis seemed excessive. On the other hand, the chosen method in this paper is re-usingideas first applied to crosswordpuzzles [21,12]. We use thepropialibrary of ECLiPSe [28] to obtain a generalized arc consistentalldifferent-sumconstraint by simple program annotation. We show that for the problem considered this is competitive with state of the art constraint libraries written in C++.

3 Initial ModelThe initial model for solving the Kakuro puzzle with finite domain variables is

fairly straightforward. For each white cell, we introduce afinite domain variable which ranges over values from 1 to 9. For each hint over a continuous horizontal (or vertical) block of variables we introduce analldifferentand asumconstraint. Slightly more formally, a Kakuro puzzle is defined by a tuple< G,H >with Ga set of cell locations, and H a set of hints given as tuples< I,v >with a positive integervand a setI?G. The model then consists of variablesxi i?G:xi?[1,9] and two types of constraints. Thealldifferentconstraint states that a set of variables must be pairwise different ?H:alldifferent({xi|i?I}) Thesumconstraint states that the sum of the variables in a hint mustbe equal to a given integer value. ?H:? i?Ix i=v Together with a search routine, this defines a model of the problem. We use the built-insearchprocedure of theiclibrary of ECLiPSe 5.10 with default values and impose a timeout of 300 seconds. Note that we don"t use anyclever method for variable or value selection. As we want to solve the puzzle without search at all, the search routine only serves as a backstop. A generic technique which helps the reasoning for many puzzles isshaving[10], already used for Sudoku in [18]. Before starting search it tests for each variable and each value in its domain if the value can be assigned to thevariable. If the assignment fails, then the value can be safely removed from the domain, strengthening the constraint propagation. This is appliedrecursively until no more domain reduction can be achieved. For logical puzzles the time required for shaving usually is well spent, as it removes possible dead-ends and helps with propagation and variable selection. Most human puzzle solvers frown upon the use of shaving as a deduction method, since it tests out values and therefore "performs search". On the other hand, it is a very effective technique which only uses polynomial time.

4 Evaluation

We test our model on a selection of puzzles from different sources: bigA single very large puzzle instance from Nikoli [22]. mixSome puzzles from the Penpa Mix puzzle collections of Nikoli[24]. giantsAnother puzzle collection from Nikoli, containing large scale examples [25]. kakuroA special issue from Nikoli on Kakuro [23]. jnpA collection of number puzzles [6] which contains some Kakuro instances. suzukiAnother collection of different puzzle types [19] containing a number of Kakuro puzzles. Note that some puzzle instances have multiple solutions, they are not used in our evaluation. The problem sizes range from very small (9x9 grid with 36 variables) to quite large (124 rows, 90 columns and 8339 variables). The experiments for all systems were run on a laptop with 2GHz Pentium M processor and 1Gb of memory under

Linux.

Table 2 shows the result for the basic model with a recursive shaving routine, which iterates shaving until saturation is reached (i.e. nomore elements can be removed). The search is limited by a timeout of 300 seconds.Kindicates the number of instances in the set,Setupthe percentage of problems solved at problem setup, just by constraint propagation,Shavethe percentage of problems solved after shaving andTotalthe percentage of problems solved after search. Average and maximal execution times for the solved instances are given, as well as average and maximal backtrack counts for the solved instances. SetXYKSetupShaveTotalAvg TimeMax TimeAvg BackMax Back jnp9980.00100.00100.000.010.010.000 jnp101080.0087.50100.000.030.073.8831 jnp121280.0050.00100.000.040.084.7532 mix1212120.00100.00100.000.010.020.000

Table 2.Basic Model with Shaving

None of the problems are solved by propagation alone, and even after shaving only about 80% of instances are solved. 6 of the larger instances were not solved within the given time limit. The contribution of shaving is significant. Without it, only 90% of the problems are solved within the time limit (15 unsolved instances).

5 MILP ModelTo check if the constraint approach is competitive, we have tried both (naive)

MILP and SAT formulations of the problem and tested them withtheeplex library in ECLiPSe [17] and with Minisat+ [5], a Pseudo-Boolean problem pre- processor for Minisat [4]. The MILP model uses 0/1 integer variablesyijwhich indicate if cellitakes valuej,jranging from 1 to 9. i?G,?j?[1,9]:yij? {0,1} We then have to restrict the variables for the same cell to state that exactly one of theyijvariables must be one, i.e. one of the values from 1 to 9 must betaken.

This is expressed with a set of equations:

i?G:? j?[1,9]y ij= 1 The next constraint type states that cells in the same block must contain different values, i.e. that valuejcan only be taken once for all cells in the index set of a hint. ?H,?j?[1,9]:? i?Iy The last constraint type expresses the arithmetic constraints, stating that the sum over all cells in a hint index set must be equal to the hint valuev. Since our basic model uses 0/1 integers, we need a rather lengthy linear form of the constraint: ?H:? i?I? j?[1,9]j?yij=v The model does not have a real objective function, as we are only looking for a (the unique) feasible solution. A dummy objective function min i?G? j?[1,9]y ij is used in our test runs. Alternatives do not seem to have a major impact. Table 3 shows results for the default Coin-OR[8] solver (CLP/CBC) ineplex[17] with a timeout of 300 seconds. 76 (mostly large) instances can not be solved within the timeout, only 76% of all instances are solved.

6 Pseudo Boolean Model

We can re-use the MIP model as the basis for a Pseudo-Boolean model, which is expanded into a SAT model. We use the same 0/1 variables, and only have to

GroupXYKNr VarsSolvedAvg TimeMax Time

big124901n/an/an/an/a giants3222464465.1710.8798.81241.31 giants324268742.000.00n/an/a giants324619423.000.00n/an/a jnp998366.75100.000.854.65 jnp10108572.62100.003.4110.40 jnp12128820.12100.009.5431.18 kakuro101439745.38100.001.026.90 kakuro1616441487.4595.4529.81151.25 kakuro3222184351.0027.78153.23301.24 mix121212744.00100.001.106.25 mix1616701494.0092.8623.03248.53 mix322284341.3812.503.943.94 suzuki2012441357.77100.0017.00287.30

All3132122.3375.7120.78301.24

Table 3.MILP Model Overview

transform the less or equal constraint (1) into a greater or equal constraint, as required by the data format for Minisat+. ?H,?j?[1,9]:? i?I-yij≥ -1 We rely on the automated translation of the equations and inequality constraints into clausal form in Minisat+, and do not use any of the possible control param- eters. As we only require a feasible solution, there is no objective function. Results for the combination of Minisat+ and Minisat2.0 [4,5] are shown in table 4, which report the time required to find a first solution. Proving that the solution is unique does not significantly increase execution times. Even by only using the default settings, the results are veryconsistent. All problems (up to 695000 clauses) except the largest one (5.2 million clauses) are solved within 300 seconds, with an average solution time of nearly 18 seconds. A solution for the "big" instance is not found in 10 hours.

7 Improving Propagation

It is disappointing that our basic finite domain constraint model was not able to solve all problems, but a simple reflection shows that missing constraint prop- agation is to blame. Consider a block of five cells with a sum of15. This is modelled as [X1,X2,X3,X4,X5] :: 1..9, alldifferent([X1,X2,X3,X4,X5]),

X1+X2+X3+X4+X5 = 15

SetXYKSolvedRestartConflictAvg DecMax DecAvg TimeMax Time big1249010.00n/an/an/an/an/an/a

Table 4.SAT Model Overview

There is no propagation from thealldifferentconstraint, and the bounds calcu- lated for the variables in the equality constraint k?Ix k=N are xi=N-? k?I,k?=ix k xi=N-? k?I,k?=ixk which evaluate to 11 and -21, and therefore do not constrain the variables either. But as we know that the values must be different, we can computean upper bound of 5 = 15-(1+2+3+4), i.e. we can remove values 6 to 9 from all domains. In order to achieve this propagation, we can either just pre-compute the domain restrictions as a redundant model, or consider thealldifferent-sumconstraint as a global, generalized arc consistent constraint. We try thefirst, simpler approach in the next section, and then consider thealldifferent-sumconstraint.

7.1 Domain Reduction

How do we know which values we can remove for which constraint? We can precompute this (with a simple finite domain constraint program) by considering every constraint of a given arity and fixed total sum. In 33 cases we can solve thealldifferent-sumconstraint by this domain reduction and an GACalldifferent constraint. In a further 31 cases, we can reduce the domains,without solving the constraint completely. This leaves 55 cases where no reduction is possible. Fortunately, these cases only occur sporadically in the given problem instances. The constraint of arity 9 is a special case. The only possiblesum is 45, which is reached by any permutation of nine different values, so againa GACalldifferent constraint is sufficient. By applying the domain reductions as a first step before setting up any other constraint, we dramatically improve performance, as shownin table 5. SetXYKSetupShaveTotalAvg TimeMax TimeAvg BackMax Back big1249010.00100.00100.001.761.760.000 giants324260.00100.00100.000.170.220.000 giants324610.00100.00100.000.180.180.000 jnp99850.00100.00100.000.010.020.000 jnp1010825.00100.00100.000.010.040.000 jnp121280.00100.00100.000.010.020.000 mix12121291.67100.00100.000.010.020.000 mix16167027.14100.00100.000.020.080.000 mix3222812.50100.00100.000.070.130.000

All31326.52100.00100.000.041.760.000

Table 5.Basic Model with Removed Values

Now a quarter of the problems are solved at setup, and all instances are solved after shaving, without calling the search routine. Note that the same reduction can be applied to the SAT and MILPmodels. Table 6 shows the result for Minisat+. It now solves all problem instances with an average time of 2 seconds, the maximal time required is 434seconds for the "big" instance with 2.1 million clauses. The results for MILP are also improved, but the model still only solves 95% of all problem instances within 300 seconds.

7.2 GAC alldifferent-sum

Reducing the initial domain of the variables is only a first step in improving the reasoning for thealldifferent-sumconstraint. Ideally, we want to treat it as a global constraint and enforce generalized arc consistencyin its propagation, i.e. for each constraint all unsupported values are removed as soon as possible. But writing a new global constraint for just this purpose seems excessive. Is there another way of achieving generalized arc consistency for our problem? Using ECLiPSe [28], we can use thepropia[12] library for generalized prop- agation. This is based on the observation that the number of feasible solutions SetXYKSolvedRestartConflictAvg DecMax DecAvg TimeMax Time jnp998100.001.1257.00180.254130.060.08 mix121212100.001.006.8335.001360.060.08

Table 6.SAT Model with Removed Values

to eachalldifferent-sumconstraint is limited. For two variables and sum 3 there are only two possible solutions, [1,2] and [2,1]. For nine variable (sum 45), there are 9! = 362880 possible solutions. Note that in ECLiPSe it is not necessary to generate the tables up-front. We can use the "infers" notation ofpropiashown below to state that we want to use some program as a GAC constraint[15]. alldifferent_sum(L,N):- sumup(L,Sum), (eval(Sum) #= N, alldifferent(L), labeling(L)) infers ac. For performance reasons it is essential to generate the constraints in the correct sequence, by increasing arity. This reduces the domains of the variables early, so that we don"t have to consider all possible combinations for the large arity constraints. Alternatively, if we generate the tables for all constraints, we can use ata- bleconstraint or multiple arc-consistentelementconstraint to achieve the same propagation. To reduce overall execution time, we perform the initial domain restriction before starting to set-up the constraints. As this removes inconsistent values very rapidly, we reduce the amount of work left for the more complex constraints. To reduce computation time further, we can set up thealldifferentconstraint and sumconstraints of the basic model before setting up the GAC version. This again removes some inconsistent values before the more complex reasoning is started. Table 7 shows the results for our improved ECLiPSe model, combining all techniques discussed above. SetXYKSetupShaveTotalAvg TimeMax TimeAvg BackMax Back big124901100.00100.00100.002.732.730.000 jnp998100.00100.00100.000.010.010.000 jnp10108100.00100.00100.000.010.030.000 jnp1212887.50100.00100.000.030.060.000 mix121212100.00100.00100.000.020.050.000 mix161670100.00100.00100.000.040.090.000 mix32228100.00100.00100.000.090.120.000

All31399.04100.00100.000.072.730.000

Table 7.Combined Model

The interesting result is that all but three of the instancesconsidered are now solved just by initially propagating the constraints, neither shaving nor search is required. We will consider the three remaining problem instances in section 8.

7.3 Alternative Models

To compare our ECLiPSe solution with an efficient finite domainsolver in C++, we did run our test cases using the Kakuro program written by C. Schulte and M. Lagerkvist in the Gecode[16] system. After fixing two small problems, we obtained the results shown in table 8. The Gecode program generatesregularconstraints[11] based on finite au- tomata for thealldifferent-sumconstraints, which provide GAC propagation. The average solving time for both systems is nearly identical, but the individual solving times vary significantly. The last three columns show themin,average andmaxratio of the Gecode time to the combined model in ECLiPSe. Another model using thegccconstraint with cost [14] was suggested by M. Carlsson[3] and tested with Sicstus Prolog. The propagation does not achieve

GAC for thealldifferent-sumconstraint.

8 Redundant Constraints

Only three problems remain unsolved after initial constraint propagation with an GACalldifferent-sumconstraint. Table 9 shows the relevant part of an unsolved

TimeRatio Gecode/ECLiPSe

SetXYKSetupTotalAvgMaxMinAvgMax

jnp998100.00100.000.000.010.500.831.00 jnp10108100.00100.000.030.080.672.364.00 jnp1212887.50100.000.090.480.504.2924.00 mix32228100.00100.000.140.360.601.343.60

All31399.04100.000.080.890.101.6724.00

Table 8.Gecode Model Results

puzzle after propagation (instance jnp-142). If a white cell contains a number, that value has been fixed by propagation. Otherwise, the remaining domain is shown. We are interested in the top four unsolved cells on the right hand, coloured in red, which we callA? {8,9},B? {8,9},C? {5,8},D? {6,9}. We can remove value 8 from A. If A is 8, then B must be 9 (alldifferent), and C must be 5 (alldifferent). The assignment of B to 9 removes 9 from the domain of D (alldifferent), leaving 6. But thenC+D= 11, not 14 as required by the horizontal sum. This causes a failure. Note we can only deduce this through the interaction of two horizontal and two verticalalldifferent-sumconstraints. Instead of defining specific patterns to capture such redundant constraint reasoning, we again use generalized propagation as suggested in [15] to cap- ture the interaction of row and column constraints. The program remains quite simple. For every quadruple of unsolved, intersecting pairs of horizontal and ver- tical constraints we impose theinteractconstraint shown below, which provides a restricted form of path consistency.Lis the set of variables occurring in the constraint. interact(L,L1,N1,L2,N2,L3,N3,L4,N4):- (alldifferent_sum(L1,N1), alldifferent_sum(L2,N2), alldifferent_sum(L3,N3), alldifferent_sum(L4,N4), lableing(L)) infers ac. By adding these redundant constraints to the combined modelwe solve the re- maining three problems at constraint setup, requiring neither shaving nor search.

3926145

126

17893642

5896
10 837
2327
1137
.89.. ... ..89 21

9652143

57

126114

11....5..8......6..9

4712
229
.5.

7.... ...6.8.

3 9217
24214
13277
1025
6295
.89. ... ..

78.. . .. . .

789
2154
.89.23.. ... .

Table 9.jnp-142: State after Propagation

9 Grading Puzzles

Most of the puzzle collections that we considered group the problems in multiple grades. This grading is typically based on how difficult the designer finds to solve the puzzle. As this is not only dependent on the techniques used, but also on the particular order in which the methods are applied, this is a highly subjective measure, which often leads to frustration for puzzle users.We propose a more objective measure of puzzle difficulty based on a constraint model which mim- ics human solving techniques. As a first step, the domain reduction discussed in section 7.1 is used. In addition we use a forward checking version ofalldif- ferent, and the usualsumconstraint. This models "obvious" propagation steps when values are assigned. After this initial propagation, we impose the GAC alldifferent-sumconstraints by increasing arity. This sequence is also normally used by humans, as it reduces the number of individual cases to be considered. Table 10 shows result of an evaluation with this model. Aftersetting up the ini- tial model, about 26% of all instances are solved, increasing to 99% when setting up all GAC constraints. This grading roughly corresponds tothe grade assigned by the designers, shown in columnGrade, with some notable exceptions. The "medium" mix-12-12 problems for example are actually easier than the "easy" problems of the same size. The results also show that GAC is really required for hard instances, even for the largest arity of thealldifferent-sumconstraint.

10 Eliminating Hints

For logical puzzles we are always interested if they are given in their minimal form, i.e. if they contain redundant hints. Reducing hints will make the puzzle

SetGradeXYKSetupP2P3P4P5P6P7P8P9

Table 10.Grading of Instances

more challenging, as long as it remainswell-posed, i.e. keeps a unique solution. Similar to [18], we experimented with a greedy method which removes hints one by one, until multiple solutions appear. We consider twovariants, in the completereduction we remove the hint completely from the problem, inthe partialreduction we keep thealldifferentcondition and only remove thesum constraint. Table 11 shows the result for a subset of probleminstances. We can see that for complete reduction we can remove between 3 and 16percent of all hints without loosing uniqueness, while for partial removal this increase to 6 to

37 percent.

CompletePartial

SetXYKMinAvgMaxMinAvgMax

giants3222105.516.868.4011.4214.2620.44 jnp9986.2511.0216.676.2514.4417.86 jnp101085.5610.3815.798.3312.1015.79 jnp121287.4110.1816.0710.0013.3918.52 kakuro1616443.418.4812.509.7617.6825.00 mix1212124.179.8514.2913.4621.0637.50 mix1616704.269.3513.2111.3617.5826.19

All2433.419.6016.676.2517.9837.50

Table 11.Reduction Summary

The reduced problems are significantly more difficult than theoriginal. Ta- ble 12 shows the results for the combined model on thepartialreduction. Note that now only a quarter of the problems are solved at setup, while even shaving is not sufficient to solve all reduced problems. Results for thecompletereduction are slightly better, but comparable. SetXYKSetupShaveTotalAvg TimeMax TimeAvg BackMax Back jnp99862.50100.00100.000.020.060.000 jnp1010850.00100.00100.000.030.070.000 jnp1212812.50100.00100.000.160.480.000 mix12121241.67100.00100.000.020.040.000 mix16167021.4398.57100.000.9437.020.000

All24325.5196.30100.001.0549.850.5165

Table 12.Partial Reduction Results

quotesdbs_dbs12.pdfusesText_18

[PDF] Kalender - Ereignis-Details - Freiwillige Feuerwehr Malchow

[PDF] KALENDER 13 - Anciens Et Réunions

[PDF] Kalender 2008-2009

[PDF] Kalender 2014 - Anciens Et Réunions

[PDF] Kalender 2016 Bayern - Anciens Et Réunions

[PDF] Kalendervorlagen 1 2 3 4 5 6 7 8 9 10 11 12 13 14

[PDF] Kalenderwoche 18-15

[PDF] KALI ESKRIMA / SILAT / PANANTUKAN - Anciens Et Réunions

[PDF] kaliburn - Burny Kaliburn Plasma Cutters

[PDF] Kalimba - Anciens Et Réunions

[PDF] Kalk-Buntfarbe Nr. 350 Farbkarte

[PDF] KALKSANDSTEIN

[PDF] Kalkung

[PDF] Kalo Keapara

[PDF] kalon dous a vari - Anciens Et Réunions