[gecode-users] [Help] Killer sudoku model (newbie)

[Mikael 'Zayenz' Lagerkvist]

On 3/22/06, Jean-Christophe Godart <jc at freesoft.be> wrote:
> Le 22-mars-06, à 11:46, Mikael 'Zayenz' Lagerkvist a écrit :
> > PS. For larger examples, you might not want to use linear() with
> > ICL_DOM, since it has exponential complexity.
>
> Thanks for your quick answer :-)
>
> That was actually the problem. Using ICL_DOM won't find the solution
> whereas all other icl do.

That is strange. A good idea is to do as Christian mentioned, and run
the test-suite for Gecode, to see if it compiled correctly. Using
stronger propagation (e.g., using ICL_DOM instead of ICL_BND) can
never (in the absence of bugs somewhere) remove a solution.


> Now, I'll make some tests with largers 3x3 grids.
>
> OK I know I should RTFM, but...
> Any hint on which default options to use for such a problem ?
> Also for BVAR & BVAL params to search()

I have no idea if there is any choice that is particularly good for
Killer Sudokus.

The usual suspect is BVAR_SIZE_MIN, for selecting the variable with
the minimum size. Experimenting is a good idea here.


> Then for the constrains which are now simply distinct() and linear()
> Would it help to define the sum as post( a + b + c ... == s) instead of
> linear() ?

Using post(...) is just a nicer syntactic notation for calling linear.


> When solving a Killer Sudoku by hand and logic, almost every time, we
> go through a state where the values that make up a cage are known, but
> their actual location isn't known yet.
> For instance, something like the domain of 2 vars A & B is restricted
> to a pair of values and consequently no other var that is constrained
> by a distinct() both for A & B may not containt these values and we can
> then restrict their domain to exclude this pair of value.
> In the Sudoku terminology, that's what is called naked pair, triplet or
> more generaly naked subset.
> Now, is there a better approach in the modeling of killer sudoku
> constraints, knowing that it's a very common case ?
> Would it help using IntSet ?

This kind of reasoning is performed by the domain-consistent distinct
propagator (i.e., when supplying ICL_DOM to distinct(...)), for the
generalized case.

When solving sudoku's with constraint programming, it is usually not
worth it to apply so strong propagation, since trading it for some
small amount of search will usually be quicker. For the
Sudoku-examples in Gecode, the simple ./examples/sudoku with options
-naive -icl val is the fastest. If this is the case also for Killer
Sudoku's, you will have to experiment with.


Cheers
Mikael

--
Mikael 'Zayenz' Lagerkvist, http://www.imit.kth.se/~zayenz/