Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
Das Suchergebnis hat sich seit Ihrer Suchanfrage verändert. Eventuell werden Dokumente in anderer Reihenfolge angezeigt.
  • Treffer 17 von 17
Zurück zur Trefferliste

How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem

  • It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Gennesaret Tjusila, Mathieu Besançon, Mark Turner, Thorsten Koch
Dokumentart:Artikel
Titel des übergeordneten Werkes (Englisch):Operations Research Letters
Band:54
Erste Seite:107105
Jahr der Erstveröffentlichung:2024
DOI:https://doi.org/10.1016/j.orl.2024.107105
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.