Computational Complexity of Generalized Forty Thieves

Chuzo IWAMOTO  Yuta MATSUI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.2   pp.429-432
Publication Date: 2015/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014EDL8154
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Keyword: 
computational complexity,  NP-completeness,  puzzle,  

Full Text: PDF(385KB)>>
Buy this Article




Summary: 
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.