2×n Minesweeper Consistency Problem is in P

ASIA unversity > 資訊學院 > 會議論文 > Item 310904400/5809

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://asiair.asia.edu.tw/ir/handle/310904400/5809

题名:	2×n Minesweeper Consistency Problem is in P
作者:	Shu-Chiung Hu;Shun-Shii Lin
贡献者:	National Chiao Tung University;National Taiwan Normal University
关键词:	Minesweeper;Minesweeper consistency problem;finite automata
日期:	2007-12-20
上传时间:	2009-12-15
出版者:	亞洲大學資訊學院;中華電腦學會
摘要:	Minesweeper is a popular single-player game included with Windows operating systems. Since Richard Kaye [12] proved that “Minesweeper is NP-complete” in 2000, it has been recently studied by many researchers. Meredith Kadlac [7] had showed that one-dimensional Minesweeper consistency problem is regular and can be recognized by a deterministic finite automaton. We extend the consistency problem to 2×n Minesweeper, which is two-dimensional but with its one dimension restricted to 2. We find that this problem is also tractable and design a finite automaton which can solve 2×n Minesweeper consistency problem in linear time. Hence, we are able to show that 2×n Minesweeper consistency problem is also in P.
關聯:	2007NCS全國計算機會議 12-20~21
显示于类别:	[資訊學院] 會議論文

文件中的档案:

档案	大小	格式	浏览次数
9032.pdf	265Kb	Adobe PDF	1467	检视/开启

在ASIAIR中所有的数据项都受到原著作权保护.