For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Computational Complexity of Generalized Forty Thieves
Chuzo IWAMOTO Yuta MATSUI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/02/01
Online ISSN: 1745-1361
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
computational complexity, NP-completeness, puzzle,
Full Text: PDF(385KB)>>
Forty Thieves is a solitaire game with two 52-card decks. The object is to move all cards from ten tableau piles of four cards to eight foundations. Each foundation is built up by suit from ace to king of the same suit, and each tableau pile is built down by suit. You may move the top card from any tableau pile to a tableau or foundation pile, and from the stock to a foundation pile. We prove that the generalized version of Forty Thieves is NP-complete.