文献

J-GLOBAL ID：201502283364364556   整理番号：15A0678046

簡素なアルゴリズムが如何にラテン方陣完了型パズルを近似的に解くことができるか

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

著者 (2件)： HARAGUCHI Kazuya (Fac. of Commerce, Otaru Univ. of Commerce) ,  ONO Hirotaka (Fac. of Economics, Kyushu Univ.)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 23  号： 3  ページ： 276-283 (J-STAGE)  発行年： 2015年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 多くのペンシルパズル変種の中で,ラテン方陣完了型パズル(LSCP)はパズルファンに人気がある。これらのパズルに関して,ここ10年その可解性は時間複雑性の観点から調べられた。これらのパズルの多くでは,与えられたパズル例が適切な解をもつかどうかを決定することはNP完全であることが示されている。ここでは,三つのLSCP(数独,Futoshiki,Kenken)の近似可能性について調べた。各LSCPを,ラテン方陣条件と固有条件のもと,可能な限り多くのセルを埋める最大化問題として定式化した。その後,簡素な遺伝的近似アルゴリズムを提案し,その近似比を分析した。(翻訳著者抄録)

シソーラス用語： *娯楽 ,  *計算機アルゴリズム ,  可能性 ,  *NP完全問題 ,  ゲーム理論 ,  *最大化問題 ,  *ゲーム ,  *正方形 ,  性質
準シソーラス用語： Futoshiki ,  KenKen ,  NP完全 ,  *パズル ,  *ラテン方陣 ,  可解性 ,  *近似アルゴリズム ,  時間複雑性 ,  数独 ,  複雑性

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  ゲーム理論  (KA03060T)

引用文献 (21件)：

• [1] Andersson, D.: Hashiwokakero is NP-Complete, Information Processing Letters, Vol.109, No.19, pp.1145-1146 (2009).
• [2] Béjar, R., Fernández, C., Mateu, C. and Valls, M.: The Sudoku Completion Problem with Rectangular Hole Pattern is NP-Complete, Discrete Mathematics, Vol.312, No.22, pp.3306-3315 (2012).
• [3] Colbourn, C.J.: The Complexity of Completing Partial Latin Squares, Discrete Applied Mathematics, Vol.8, No.1, pp.25-30 (1984).
• [4] Cygan, M.: Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search, FOCS 2013, pp.509-518, IEEE Computer Society (2013).
• [5] Demaine, E.D., Okamoto, Y., Uehara, R. and Uno, Y.: Computational Complexity and an Integer Programming Model of Shakashaka, CCCG 2013, pp.31-36, Carleton University, Ottawa, Canada (2013).

タイトルに関連する用語 (3件)： アルゴリズム ,  パズル ,  近似