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 uma 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 simples monocromático cujos vértices estejam livres de quaisquer fichas. O primeiro jogador a atingir um vértice que tenha sua cor é declarado vencedor.
O roadblock problem consiste no seguinte: dada uma configuração do jogo (ou seja, um grafo como o descrito acima, com fichas estacionadas em alguns vértices), decidir se existe uma estratégia vencedora para o jogador que será o próximo a jogar. (Uma estratégia é vencedora se leva o jogador a ganhar o jogo o que quer que o outro jogador faça.)
Não existe algoritmo polinomial que resolva o problema. A complexidade do problema é exponencial. (Veja o livro de Harel, p.184.)