daniel mahler wrote:
When I was thinking of writing a sudoku solver, I thought of treating the numbers as FS vaiables instead ofnstead of treating the positions as FD variables Rows, columns and blocks are (fixed) sets of positions as well. Then you just need to say the numbers are all mutually disjoint, have cardinality 9, and have a singleton intersection with each row, column and block. I though this would be nicer to code than the FD approach. Any thoughts on the relative merits of the approaches?
I tried this, but I cannot say it is nicer to code. One problem is that you need a lot more propagators than with integers: instead of 9 alldiff for the rows, 9 alldiff for the columns, and 9 alldiff for the blocks, you need 45 disjointness propagators, 81 intersections for the rows, 81 intersections for the columns, and 81 intersections for the blocks, plus cardinality restrictions for all intersections.
In my experiments, the integer model also performed much better: it solved more puzzles without search, in much less time, and with a 5th of the memory. I can't say anything about formal properties like if the integer model is always stronger, though.
Furthermore, the additional, implied constraints Helmut Simonis proposed are quite hard to model in the set case, I think.
Cheers, Guido _________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
