Voltar
Capítulo de livro Revisado por pares
BIBTEX RIS

The complexity and decidability of separation

1984; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-13345-3_10

ISSN

1611-3349

Autores

Bernard Chazelle, Thomas Ottmann, Eljas Soisalon-Soininen, Derick Wood,

Tópico(s)

Digital Image Processing Techniques

Resumo

We study the difficulty of solving instances of a new family of sliding block puzzles called SEPARATION TM. Each puzzle in the family consists of an arrangement in the plane of n rectilinear wooden blocks, n > 0. The aim is to discover a sequence of rectilinear moves which when carried out will separate each piece to infinity. If there is such a sequence of moves we say the puzzle or arrangement is separable and if each piece is moved only once we say it is one-separable. Furthermore if it is one-separable with all moves being in the same direction we say it is iso-separable. We prove:

Referência(s)