General

• A survey of NP-complete puzzles 2008
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• Complexity and completeness of finding another solution and its application to puzzles
  • Slither Link, Cross Sum, Number Place
• Computational Complexity of Games and Puzzles

Algorithms

Single agent

• Slither Link

  • An algorithm for automatic generation of the Slither Link problems 1998
  • On the NP-completeness of the Slither Link Puzzle (japaness) 2000 Yato Takayuku
  • A rule-based approach to the puzzle of Slither Link 2005
  • Solving and Making Problems of Slither Link 2006
  • 數迴解題器 2009 蘇粲程
  • LPL
    • The Slitherlink Puzzle 2008
  • Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs
  • Solving the Slitherlink Problem 2012

• Light Up

  • Light Up is NP-complete 2005
  • Light Up遊戲一致性問題之研究 2007 王怡人
  • A Simple and Rapid Lights-up Solver 2009 S.J. Yen, S.Y. Chiu

• Nurikabe

  • The complexity of puzzles: NP-completeness results for Nurikabe and Minesweeper 2003 Brandon McPhail
  • On the NP-completeness of the nurikabe pencil puzzle and variants thereof
  • Computational Complexity of NURIKABE
  • Nurikabe, Heuristic Search, Puzzle 2009 S.J. Yen, T.D. Chuang, S.Y. Chiu, J.C. Chen
  • Generating and Auto-solving

• Fillomino

  • An efficient algorithm for solving Fillomino 2011 Shi-Jim Yen, Tsan-Cheng Su and Shun-Chin Hsu
  • Solving Fillomino With efficient Algorithm

• Shikaku

• Hitori

• Hitori Solver 2009 Shi-Jim Yen, Tsan-Cheng Su, Shih-Yuan Chiu

Hashi

• Elimination search for puzzle games: An application for Hashi solver 2011 Shi-Jim Yen, Shih-Yuan Chiu, Cheng-Wei Chou, Tsan-Cheng Su

• Sokoban

  • http://webdocs.cs.ualberta.ca/~games/Sokoban/papers.html
    • Pushing the Limits: New Developments in Single-Agent Search 1999 Andreas Junghanns
  • Sokoban is PSPACE-complete 1998
  • 倉庫番遊戲之最少搬移演算法分析與研究 2002 蔡明原
  • Sokoban: Reversed Solving 2008
  • Towards deadlock free Sokoban 2010
  • Difficulty Rating of Sokoban Puzzle 2010
  • generation
    • Procedural Generation of Sokoban Levels

• 三角殺棋 Triangular Nim

  • 利用電腦探討七層三角殺棋的勝負問題 1985
  • 八層三角殺棋的勝負問題之研究 白聖群 2008
  • 對局理論 期中作業 三角殺棋 林宏軒 2008
  • 八層及九層三角殺棋的勝負問題之改進與研究 陳俊佑 2009
  • Solving 9 Layer Triangular Nim 2010
  • Solving Nine Layer Triangular Nim

Masyu

Samegame

Rush hour

FreeCell

• More

• Nonogram

Multi agent

• Perfect information

  • 台灣直棋

    • 台灣直棋的勝負問題之研究 2010 李明臻

• Master Mind, AB Game

  • Optimal algorithms for 2×n Mastermind games - a graph-partition approach 2004
    • 演繹競局及相關問題最佳化演算法之研究 2004
  • Novel Algorithms for Deductive Games 2004
  • Strategy optimization for deductive games 2007
  • A Two-Phase Optimization Algorithm for Mastermind 2007
  • An Efficient Approach to Solve Mastermind Optimally 2007
  • Optimal Analyses for 3×n AB Games in the Worst Case 2010
    • 較高維度演繹競局問題最佳演算法之設計與分析 2008
  • [猜數字系列] 和大家分享我最近寫的猜數字…… ( 最佳解求出來了 5.2131 ) owenlin_twn
  • with a lie
    • Exact-bound analyses and optimal strategies for Mastermind with a lie 2006

• Inperfect information

  • Bridge

    • The State of Automated Bridge Play 2010
    • GIB: Steps Toward an Expert-Level Bridge-Playing Program

• 麻將 Mahjong

  • 麻將之人工智慧研究 2008 林典餘
  • Tournament Framework for Computer Mahjong Competitions 2011

• 大老二

  • 電腦大老二程式之設計與實作 2010 廖耕毅

• 十三張

  • 電腦十三張程式之設計與實作 2007 簡銘均
  • 電腦十三張程式之牌招探討 2008 殷振軒

• 蜜月橋牌

  • 不完全資訊賽局蜜月橋牌之研究 2008 葉俊廷

• Texas Hold'em Poker

  • A Competitive Texas Hold'em Poker Player Via Automated Abstraction and Real-time Equilibrium Computation 2006
  • Potential-aware Automated Abstraction of Sequential Games, and Holistic Equilibrium Analysis of Texas Hold'em Poker 2007
  • Better automated abstraction techniques for imperfect information games, with application to Texas Hold'em poker 2007
  • 「德州撲克」不完全資訊賽局之研究 2006 張瓈文

• Liar Dice

  • 吹牛骰子之人工智慧研究 2008 黃信翰

search

• 林順喜
• 顏士淨
• 吳毅成