Sudoku as a Constraint Problem H. Simonis IC

Sudoku as a Constraint Problem H. Simonis IC

Sudoku as a Constraint Problem H. Simonis IC Parc Overview Page 2 Problem Contribution Different forms of alldifferent

Shaving Redundant constraints Evaluation Copyright 2005, IC Parc Sudoku Each row, column and major block must be alldifferent Well posed if it has unique solution Page 3 Copyright 2005, IC Parc Contribution Analysis of Sudoku as a constraint problem Solve problem only by propagation Unique solution

Search considered unfair Modest improvement of propagation of multiple alldifferent constraints Comparison of available Sudoku collections Most published puzzles contain (many) redundant hints Generating puzzles of given difficulty Page 4 Copyright 2005, IC Parc Model for problem of order N (typical 3) N2 x N2 matrix Domains 1..N2 3* N2 alldifferent constraints Rows

Columns Major blocks No symmetries Page 5 Copyright 2005, IC Parc Forms of alldifferent (van Hoeve 2001) FC (Forward checking, Haralick 80) BC (Bound Consistency, Puget 98) HAC (Hyper-arc consistency, Regin 94)

FCI: 2xFC + Channeling (Cheng 96) Needs inverse constraint (Beldiceanu 2005) Simple hyper arc-consistent implementation BCI: 2xBC + Channeling Page 6 Copyright 2005, IC Parc Shaving Classical technique when constraints are not strong enough Test if variable can be set to value If this fails, you can remove value from domain Often used in scheduling (Torres 2000) Only test smallest and largest value

Here Test all values Test all variables (once, not recursive) FCV, BCV, HACV: Shaving + FC, BC, HAC Page 7 Copyright 2005, IC Parc Redundant constraints Colored matrix (Regin 2004)

Same with cardinality (Beldiceanu 2005) Rows/Blocks interaction Rows/Columns/Blocks? Looks like 3D Matching Linear relaxation Bilocation/Bivalue graph (Eppstein 2005) Page 8 Copyright 2005, IC Parc HACC: Colored matrix(Beldiceanu 2005) Cardinality matrix (Regin & Gomes 2004) One constraint per value

Matching between rows and columns Page 9 Copyright 2005, IC Parc HACS: Same with cardinality (Beldiceanu 2005) Sets x14,x15,x16,x17,x18,x19 x21,x22,x23,x31,x32,x33 must use the same values A value in one of the sets which does not occur in the other can be removed Page 10

Copyright 2005, IC Parc HAC3: Rows(Columns)/Blocks overlap 54 matching problems of this form: Page 11 Copyright 2005, IC Parc Lattice of model alternatives No difference detected Strongest Fastest

Page 12 Copyright 2005, IC Parc Evaluation Available Sudoku sources Newspaper collections (all 2005) The Times The Daily Telegraph The Guardian

The Independent The Daily Mail The Sun Puzzle magazines (Nikoli, 1988-2005) How-to books (all 2005) Vorderman Wilson Sinden Huckvale Sudoku Fandom (all 2005)

Page 13 Royle (>7000 instances) Stertenbrink Eppstein (>30000 instances) Copyright 2005, IC Parc Results with propagation The Times The Daily Telegraph The Guardian The Independent The Daily Mail The Sun

Nikoli Big Book Little Book Wilson Vorderman Page 14 Fandom Copyright 2005, IC Parc Results with shaving The Times The Daily Telegraph The Guardian The Independent The Daily Mail

The Sun Nikoli Big Book Little Book Wilson Vorderman Page 15 Fandom Copyright 2005, IC Parc Proposed problem grading Grade Searchfree with

Beginner FC Easy 2xFC + Channeling Medium HAC Difficult HAC + Same + Colored Matrix Challenge

HAC + Shaving Monster None known Page 16 Copyright 2005, IC Parc Further work LP relaxation Suggested in Regin&Gomes Bilocation/Bivalue graphs (Eppstein 2005) Significantly stronger than redundant constraints presented here

Rows/Columns/Blocks interaction Is this possible? Page 17 Copyright 2005, IC Parc Conclusions Millions of constraint programmers out there Perfect to explain to your partner what you are working on Propagation alone Good test for reasoning power Something to be learnt from Sudoku community Rediscovery of many CP concepts (they are simple) Very efficient (non-systematic) FD implementations

New constraint reasoning for interacting alldifferent constraints Many (too many?) modelling variants for rather simple problem Daily Telegraph has most challenging puzzles May be not reason enough to buy the paper Page 18 Copyright 2005, IC Parc

Recently Viewed Presentations

  • A Public Health Approach to Alzheimer's and Other Dementias

    A Public Health Approach to Alzheimer's and Other Dementias

    A Public Health Approach to Alzheimer's and Other Dementias. Alzheimer's & Other Dementias - The Basics. DISCLAIMERS. This publication was supported by Cooperative Agreement Number 5U58DP002945-05, funded by the Centers for Disease Control and Prevention.
  • Catalyst for Health and Safety: Strategies to address

    Catalyst for Health and Safety: Strategies to address

    The Cost of IPV. The medical cost burden within the 12 months after victimization ranges from $2 to $7 billion nationally. Without intervention, higher health care costs persist even 3 to 5 years after DV exposure has ended.
  • Probabilistic Inference - Duke University

    Probabilistic Inference - Duke University

    Making more independence assumptions always makes a probabilistic model less expressive. If the independence relationships assumed by structure model A are a superset of those in structure B, then B can express any probability distribution that A can. X. Y....
  • Agus Gobbetti Marton Pintore Vazquez - EG2017 Tutorial 4 ...

    Agus Gobbetti Marton Pintore Vazquez - EG2017 Tutorial 4 ...

    WinPhone & iOS requires less effort for distribution. Easy to reach the whole user base. Android has a wide variety of configuration that require tuning. User base is typically reached in an incremental way (supporting more configs) Many HW configurations...
  • Outdoor learning for health and wellbeing

    Outdoor learning for health and wellbeing

    Resources to explore… 1. Wild Pedagogies- Touchstones for Re-Negotiating Education and the Environment in the Anthropocene Editors: Jickling,B., Blenkinsop, S., Timmerman, N., De Danann Sitka-Sage, M. 2. ID guides eg - collins complete guide to british trees
  • PPFE: clinico-pathological entity or non specific reaction Elisabetta

    PPFE: clinico-pathological entity or non specific reaction Elisabetta

    Two independent radiologists scoring CTs in randomized order, independently. To limit overcalling of trivial PPFE, all cases in which the maximum lobar score identified by both scores was mild (1), and all those in which only one of the two...
  • Process Mapping

    Process Mapping

    Display the process map in the relevant clinical area and encourage all staff to amend/update and put forward ideas for improvement. Type up the process map, issues and ideas and send out to all participants with a date for a...
  • Allgemein - Free

    Allgemein - Free

    Times New Roman Arial Monotype Sorts Times PhoneticOxSans IPAsans Allgemein (Standard) Microsoft Word-Dokument A History of the English Language Time Line 1 Time Line 2 Political, Cultural, and Technological Influences The Self-Conscious Language The Debate over Vocabulary Inkhorn terms vs....