Roadblock problem
(Veja o livro de Harel, p.184.)
Imagine um grafo cada uma de cujas arestas tem uma de três cores: vermelho, azul ou amarelo. Alguns vértices do grafo são pretos, outros são brancos, e outros não têm cor alguma.
Há dois jogadores, Preto e Branco. Cada jogador tem um certo número de fichas: Preto tem fichas pretas e Branco tem fichas brancas. Cada ficha está estacionada sobre algum vértice e há no máximo 1 ficha em cada vértice.
Os dois jogadores se alternam movimentando suas fichas de acordo com a seguinte regra: em cada jogada, um jogador move uma de suas fichas para um novo vértice ao longo de um caminho monocromático cujos vértices estejam livres de quaisquer fichas. O primeiro jogador a atingir um vértice que tenha a sua cor é declarado vencedor.
O problema da barreira (roadblock problem) consiste no seguinte: dada uma configuração do jogo (ou seja, um grafo como o descrito acima, com fichas estacionadas nos vértices), decidir se existe uma estratégia vencedora para o próximo jogador a jogar.