A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Calculation Solitaire is NP-Complete Solitário de Cálculo é NP-Completo

Chuzo IWAMOTO, Tatsuya IDE

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Cálculo é um jogo de paciência com um baralho padrão de 52 cartas. Inicialmente, as cartas A, 2, 3 e 4 de qualquer naipe são dispostas como quatro bases. As 48 cartas restantes são empilhadas como estoque e há quatro pilhas vazias do tabuleiro. O objetivo do jogo é mover todas as cartas do estoque para as fundações. A base começando com A deve ser construída na sequência de um ás até um rei. As outras fundações são construídas de forma semelhante, mas em pares, três e quatro, de 2, 3 e 4, até que um rei seja alcançado. Aqui, uma carta de classificação i pode ser usado como uma carta de classificação i + 13j for j ∈ {0, 1, 2, 3}. Durante o jogo, o jogador move (i) a carta do topo do monte para uma fundação ou para o topo de uma pilha do tabuleiro, ou (ii) a carta do topo de uma pilha do tabuleiro para uma fundação. Provamos que a versão generalizada do Calculation Solitaire é NP-completa.

Publicação
IEICE TRANSACTIONS on Information Vol.E106-D No.3 pp.328-332
Data de publicação
2023/03/01
Publicitada
2022/10/31
ISSN online
1745-1361
DOI
10.1587/transinf.2022FCL0002
Tipo de Manuscrito
Special Section LETTER (Special Section on Foundations of Computer Science — Foundations of Computer Science Supporting the Information Society —)
Categoria

autores

Chuzo IWAMOTO
  Hiroshima University
Tatsuya IDE
  Hiroshima University

Palavra-chave