How Simple Algorithms Can Solve Latin Square Completion-Type Puzzles Approximately

• Haraguchi Kazuya

  Faculty of Commerce, Otaru University of Commerce

• Ono Hirotaka

  Faculty of Economics, Kyushu University

Abstract

Among many variations of pencil puzzles, Latin square Completion-Type puzzles (LSCPs) are quite popular for puzzle fans. Concerning these puzzles, the solvability has been investigated from the viewpoint of time complexity in the last decade; it has been shown that, in most of these puzzles, it is NP-complete to determine whether a given puzzle instance has a proper solution. In this paper, we investigate the approximability of three LSCPs: Sudoku, Futoshiki and Kenken. We formulate each LSCP as a maximization problem that asks to fill as many cells as possible, under the Latin square condition and the inherent condition. We then propose simple generic approximation algorithms for them and analyze their approximation ratios.

Journal

• Journal of Information Processing

  Journal of Information Processing 23 (3), 276-283, 2015

  Information Processing Society of Japan

Keywords

• Latin square Completion-Type puzzles
• approximation algorithms
• Sudoku
• Futoshiki
• Kenken

Details

• CRID: 1390001205295208576
• NII Article ID: 130005070055
• NII Book ID: AA00700121
• ISSN: 03876101
• ISSN: 18826652
• DOI: 10.2197/ipsjjip.23.276
• Web Site: http://hdl.handle.net/10252/5462
• Web Site: https://www.jstage.jst.go.jp/article/ipsjjip/23/3/23_276/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed