Puzzle8 é um jogo num tabuleiro de 3x3, em que uma das casas está vazia. Os movimentos possíveis a cada momento é mover para a casa vazia, o conteúdo de uma das casas ao lado. O objetivo é colocar o tabuleiro numa posição final. Para evitar alguns ciclos, pode-se não considerar o sucessor que volta para trás.

3 movimentos de exemplo desde a posição inicial:

 A procura em profundidade vai expandir primeiro os estados gerados há menos tempo, antes dos restantes.

Ficheiro de Excel, passo a passo:

Nesta procura houve 12 estados gerados, e 8 estados expandidos. Foi encontrada a solução que passa pelos estados 12, 10, 3, 1. 

O que está nesta tabela e o que significam as cores? O código de cores significa que primeiro foi criado o estado 1 a vermelho, de seguida após a expansão 1 foram criados os estados 2 a 4 a verde, após a expansão 2 foi criado o estado 5 a azul. Da expansão 3 resultaram a vermelho os estados 6 e 7, as expansões 4 e 5 não resultaram novos estados dado que foi atingido o limite (nível a zero), e da expansão 6 foram gerados os estados 8 a 10 a verde. Os estados 11 e 12 a azul foram gerados na expansão 7.   

Vendo a tabela mais em detalhe:

• Na linha 1 está o estado inicial, ou seja, a posição que obtivemos quando desfizemos a posição inicial com 3 movimentos. Ora como partimos da posição inicial, sabemos que há uma solução em 3 movimentos, pelo que garantidamente com um algoritmo em profundidade limitado a nível 3 encontraríamos sempre uma solução. 
• Na primeira coluna está o número do estado, ou o número da geração do estado. Na segunda coluna está o estado em si. Como o algoritmo tem um nível de profundidade, guardamos na terceira coluna a informação do nível em que está a procura, marcando o estado inicial com o valor a que queremos fazer a procura, o valor 3, e sempre que gerarmos um estado, diminui-se este valor relativo ao valor do nível do estado pai. Na quarta coluna temos a informação do pai do estado, ou seja, o número do estado a partir do qual esse estado foi gerado, e no final temos o número de ordem de expansão.
• Começamos por expandir o primeiro estado, na linha 1, dando origem aos estados das linhas 2 a 4. O algoritmo prossegue expandindo não a linha 2, mas a última linha, a linha 4, daí o número de expansão da linha 4, resultando na linha 5. Notar que o movimento inverso, que levava à posição inicial, não foi gerado, dado que se assume essa optimização, que evita alguns ciclos. A implementação desse teste é simples, dado que existe um campo em cada estado indicando o pai, pelo que se se gerar um filho igual ao pai, este pode ser imediatamente anulado.
• Prosseguindo, expande-se a linha 5, que gera as linhas 6 e 7, já com nível 0. Significa que ou são solução final, ou não se pode gerar mais sucessores a partir desses estados, de forma a respeitar o limite de profundidade imposto. É o que acontece, expande-se a linha 7 e de seguida a linha 6, mas sem adicionar sucessores, apenas verificando se é um estado final. O último estado gerado mas não expandido, passa a ser o estado 3, que é expandido agora, em 6º lugar, gerando as linhas 8 a 10. Expande-se agora a linha 10, gerando as linhas 11 e 12, e ao expandir a linha 12 verifica-se que esta é um estado solução. O algoritmo pára, podendo reconstruir o caminho desde o estado inicial até ao estado final através da indicação dos estados pai.