Changes

Esse capítulo é dedicado aos aspectos computacionais do estudo das árvores. Árvores são um tipo específico de grafo, que são conectados grafos conexos simples que não tem circuitos simples.

Se esse comando não produzir retornar uma descrição da versão, então vocês está utilizando a versão errada. Uma versão apropriada pode ser encontrada no site ftp: http://www.mhhe.com/math/advmath/rosen/r5/instructor/maple.html junto com instruções de instalação.

Primeiro, nós iremos discutir como representar, desenhar, e trabalhar com árvores usando o Maple. Especificamente, nós iremos descrever como representar e construir árvores e derivar características básicas sobre árvores em Maple. Nós iremos demonstrar como utilizar o Maple para desenhar árvores.Nós iremos Iremos também demonstrar como resolver vários problemas, onde árvores fazem desempenham um papel importante usando Maple, como procurando procurar e construindo construir códigos prefixos, usando uma implementação específica do algoritmo de Huffman. Nós iremos Vamos descrever como usar o Maple para fazer diferentes métodos de percorrer uma árvore, onde sendo o percurso é a visita dos vértices da árvore em uma ordem pré-definida. Então nós iremos discutir como esses percursos se relacionam com o tópico de organização. Continuamos mostrando como usar o Maple para criar spanning trees árvores de extensão de grafos. Então, nós iremos mostrar como usar o Maple como para resolver vários problemas utilizando backtracking. Finalmente, iremos mostrar como encontrar spanning trees árvores de extensão de peso mínimo de grafos ponderados usando Maple.

Para começar, iremos demonstrar como construir árvores em Maple. Dada uma árvore sem raiz, nós podemos construir essa árvore em Maple assim como faríamos com qualquer grafo. Nós também iremos dar um procedure que usa algumas capacidades embutidas alguns comandos do Maple que determinam se um grafo específico é uma árvore.

Antes de entrar na implementação, há dois pontos importantes que devem ser mencionados. Primeiro, notamos que o Maple difere da terminologia de texto, no senso que o Maple refere-se a ciclos simples ciclos, quando enquanto o texto se refere a circuitos simples circuitos. O segundo ponto que vale mencionar é de que uma árvore sem raiz é um grafo simples que não tem ciclos simples. Estruturalmente falando, uma árvore com raiz é exatamente a mesma coisa que uma árvore sem raiz, com a propriedade adicional de que há um vértice específico chamado de raiz, que é visto como o ponto inicial de uma árvore. Em termos de implementação Maple, representamos árvores sem raiz como grafos, e criamos árvores sem raiz a partir de árvores sem raiz utilizando comandos Maple como spantree, que serão abordados posteriormente, especificando um nó desejado uma raiz desejada para uma árvore sem nó.

Outro tipo importante de árvore é a árvore ordenada, que é uma árvore com raiz onde os filhos de um vértice ordenados de alguma maneira como 1stprimeiro, 2ndsegundo,...,mn-th ésimo filhos se houverem m n filhos de um dado vértice. Nós iremos fazer Faremos uso do peso dos vértices para determinar a ordem dos filhos de um vértice específico. Esse tipo de árvore irá aparecer posteriormente, mas é importante distinguir árvores sem raiz, com raiz e desordenadas, e árvores com raiz e ordenadas.

Como primeiro exemplo, iremos discutir árvores sem raiz. Criamos uma árvore exatamente da mesma maneira que criamos um grafo, usando o pacote networks do Maple. Como nosso primeiro exemplo, iremos criar uma árvore simples em com 4 vértices.

1.O grafo é conectadoconexo.

Usando Maple, essas propriedades são facilmente verificadas. Em particular, podemos determinar se um grafo é conectado em Maple usando o comandoscomponentscomando components, que retorna uma coleção de conjuntos de vértices, onde cada conjunto nessa coleção contém os vértices de um componente conexo do grafo. Podemos determinar se um grafo é simples usando o comando Maple gsimp, que retorna a árvore simples por baixo de um multigrafo(ou pseudografo), e então comparando o número de arestas da árvore por baixo do grafo original. Isso nos leva até o procedure IsSimple.

Note que não devemos simplificar G por si só, pois tal simplificação é um processo irreversível.

Se você preferir, pode substituir o teste cycle base test nesse procedure por um que verifica se o número de arestas é um a menos que o número de vértices.

Agora estamos prontos para usar o procedure IsTree para determinar se alguns grafos particulares são árvores;

Até esse ponto, nós lidamos apenas com árvores sem raiz. Podemos usar o comando Maplespantree para mudar transformar uma árvore sem raiz em uma árvore com raiz. Ele faz isso atualizando os conjuntos de ancestrais e filhas (descendentes) para cada vértice, para refletir imitar a estrutura da spanning treeárvore de extensão.

Para usar o comando spantree, devemos selecionar o um vértice e formar uma spanning tree com árvore de extensão usando esse vértice como raiz, direcionando todas as arestas na da árvore em direção a raiz. (Estudaremos spanning trees árvores de extensão mais tarde nesse capítulo. Geralmente, o comando spantree pega um grafo conexo indireto G e um vértice v e constrói uma spanning tree árvore de extensão de G usando v como a raiz, direcionando todas as arestas em direção a v.) Por exemplo, podemos transformar a árvore T1 em uma árvore com raiz, tomando a como sua raiz e utilizando o comando:

Agora representamos apresentaremos um procedure que encontra todos os descendentes, ancestrais e irmãos de um vértice particular em uma árvore com raiz. Esse procedure, chamado Family, pode ser descrito usando o seguinte pseudo-códigopseudocódigo:

1. Para encontrar todos os ancestrais, usamos o comando ancestor do Maple até que não haverem hajam mais ancestrais (ex: quando atingimos o vértice raiz).

2. Para achar todos os descendentes, usamos o comando daughter repetidamente até que não haverem hajam mais descendentes(ex: quando todas as folhas de um vértice forem atingidas).

Uma implementação desse procedure é como a se dá da seguintemaneira:

Agora iremos construir uma árvore mais largamaior, chamada T3 que é a árvore mostrada na Página 5433 do texto, e então iremos executar o novo procedure criado em um de seus vértices.

Os descentendes descendentes do vértice B são obtidos pelo comando:

A seguir, determinamos o conjunto de vértices internos (galhos) e folhas de uma árvore com raiz. Lembre-se que um v é um vértice interno de uma árvore com raiz se v tiver filhos, e que v é o vértice folha de uma árvore com raiz se v não tiver filhos. Em outras palavras, em qualquer árvore com raiz não trivial (ex:.uma árvore com raiz que é mais do que apenas um vértice raiz), as folhas são essas com gráu de vértice grau 1, e os vértices internos são vértices com grau maior que 1.

Agora iremos discutir como encontrar o maior número de filhos de um vértice interno de uma árvore com raiz. Lembre-se que se m é esse número, a árvore é chamada de árvore m-ária. Também iremos descrever como determinar se uma árvore m-ária é balanceadobalanceada. Lembre-se que uma árvore é balanceada se todas as folhas estão no nível h ou h-1 se , sendo essa uma árvore tem com um total de h níveis, onde o nível do vértice é a distância do caminho único from da raiz até tal vértice.

Para utilizar o Maple para determinar se uma árvore é uma árvore m-ária, podemos simplesmente olhar a sequencia sequência de graus do vértice, tomando em conta que para todos os vértices exceto a raiz, o grau de tal vértice é um a mais que o número de descendentes. Isso pode ser feito usando o comando vdegree no Maple. Para determinar se uma árvore é balanceada, podemos usar a estrutura de armazenamento interno de uma árvore em no Maple. Iremos utilizar do fato de que o Maple armazena o nível do vértice em uma árvore como o peso do vértice para esse vérticeele mesmo. Por exemplo, se v é um vértice que está no nível 3 de uma árvore, então podemos extrair essa informação usando o comando vweight no vértice v.

Esaa Essa técnica é formalizade formalizada pelo seguinte procedure no Maple:

Agora iremos utilizar o procedure ArityBalanced para verificar a fórmula na página 541 do texto para árvore árvores m-árias cheias. Isto é, iremos construir um procedure para computar o número de vértices internos e folhas de dada árvore m-ária, e comparar essas quantidades como esboçado no teorema 3 e teorema 4 da página 541 do texto. O procedure chamado TheoremVerify utilizará:

Se o vértice não houverem tiver filhos do vértice, ele é uma folha

Utilizaremos o procedure TheoremVerify para verificar os teoremas 3 e 4 do texto em uma árvore 3-ária (ternária) completa.

Essa sessão foca no uso de árvores em árvores binárias de busca binárias. Especificamente, chamamos o uso de árvores em algoritmos de busca binária assim como o uso de árvores em código no algoritmo de Huffman. A razão pela qual desejamos usar árvores binárias é de que podemos usar a binary estrutura binária da árvore para tomar decisões binárias(ex: true/false) quanto a inserção ou procura de caminhos.

Uma árvore é chamada de árvore binária se todos os vértices na árvore tiverem no máximo dois filhos. Nesse capítulo, iremos utilizar árvores binárias ordenadas. A ordenação dos vértices é simplesmente a marcação dos filhos de um vértice como o filho a à esquerda ou o filho a à direita, onde o filho a à esquerda é considerado o filho que deve ser visitado primeiro, e o da direita, o que deve ser visitado em segundo.

Click here to access a summary of all the Maple code used in this section.Um benefício crucial em árvores binárias ordenadas é de que o tempo de buscar busca exigido to para encontrar um específico elemento da árvore é logarítmico no ao número de vértices da árvore. A maior desvantegem desvantagem é de que a inserção de um vértice é muito mais taxativa. Discutiremos estes aspectos em mais detalhe enquanto percorremos a própria impementação implementação de um algoritmo de inserção binária.

Requerimos marcações no vérticeOs vértices devem se marcados. No Maple podemos utilizar o nome do vértice como marcação já que ele pode ser tanto inteiro como string.

Um vértice tipico na árvore tipicamente tem dois descendentes (filhas). Devemos ser capazes de especificar quais qual desses dois vértices é o descendente da esquerda e qual é o da direita. Podemos indicar isso utilizando o peso do vértice. No Maple, cada vértice tem um peso padrão de 0, como demonstrado no simples exemplo:

Ela também facilita a mudança do critério de comparação em outro ponto posteriorcaso seja necessário mais tarde, refazendo sem ter que refazer totalmente o código do algoritmo inteiro.

Também precisaremos ser capazes de achar a raiz da árvore. O seguinte procedure calcula tal raiz e força a árvore a lembrar sua raiz, para que a sua computação não precise ser repetida.

O procedure para construir uma árvore binária ordenadapor ordenada por inserção é acontece como o exemplo seguinte. Para facilitar, utilizamos o nome do vértice como seu valor quando fazemos comparaçãoestivermos comparando.

3. Caso contrário, transforme a raiz da árvore na variável para o vértice atual cur_vertex, e compare v com cur_vertex. se Se v =cur_vertex, está feitoacabado.

4. se v <cur_vertex então procure o filho a à esquerda, caso contrário, procure o filho a à direita. Isso é feito mudando cur_vertex para ser o filho a à esquerda ou a à direita e comparando o novo cur_vertex com v.

As ordenações relativas dos descendentes e , x e cur_vertex determinam se x pode ser inserido como folha.

não há filhos, então adicione apenas um novo filhovértice.

Para todos os casos restantes adicione em x como um novo vértice

O procedure addvertex é usado aqui em de uma maneira que atualiza os pesos de cada vértice na medida que ele é criadoeles são criados. Isso serve para indicar se é o vértice é um descendente a à esquerda ou a à direita. Enquanto não usamos esses pesos, eles poderiam ser utilizados como uma medida alternativa para ordenação de descendentes de qualquer vértice particular.

Ao invés disso, para a ordenação, nós usamos os nomes dos vértices para indicar a ordenação relativa dos vértices. O fato de que qaiquer quaisquer dois vértices (e não apenas descendentes do mesmo vértice) podem ser comparados nos permite combinar o novo vértice, os descendentes, e o vértice atual tudo em uma lista ordenada a qual que é então inspecionada para determinar qual dos vários casos especiais é relevante durante a inserção de um novo vértice. Qualquer que seja o método de comparação de vértices que for utilizado, é importante que o procedure de comparação seja passado na rotina de ordenação como um argumento extra.

Árvores binárias existem para serem procuradasusadas como método de busca. O seguinte procedure BiSearch a seguir faz isso. Declarações do tipo Print foram adicionadas para ilustrar o caminho que o algoritmo usa enquanto faz a busca na árvore.

A codificação de Huffman é um método para construir um código prefixo eficiente para um conjunto de caractéres. Ele é baseado num Nesse algoritmo ganancioso, onde em cada passo os vértices com menos peso são examinados. A codificação de Huffman pode produzir códigos de prefixo em condições óptimasideais. O seguinte pseudo-código pseudocódigo descreve um algoritmo para codificação de Huffman. (Para uma discussão mais completa sobre a codificação de Huffman, veja Cormen, Leiserson, e Rivest, Introduction to Algorithms, MIT Press, 1989.)

Comece criando uma lista ordenada de elementos a serem codificados, onde a que tem ordenação é com respeito a frequência de ocorrência desses elementos. Considere cada elemento da lista como um vértice com peso igual a sua frequência de ocorrência.

2. Atribua x como o filho a à esquerda e y como o filho a à direita de um novo vértice em nossa árvore;

Por examploexemplo, descobrimos que [b,10] < [a,15].

O tipo listlist denota uma lista de listas. O eval no final é incluído para garantir que o resultado retornado pelo procedure é a própria árvore, e não apenas seu nome.

Teste esse novo procedure na seguinte lista de caractéres em inglês emparelhados com uma frequência relativa de ocorrência;

Os pesos adicionados aos vértices aqui representam o número que desse vértice em termos de relação a seu pai. Por exemplo, d é o terceiro filho de a. Como nas seções anteriores, tais pesos poderiam ser usados para ordenação, apesar de que em fatona verdade, a ordenação por baixo é simplesmente alfabético alfabética nos nomes dos vértices. Primeiro implementamos o algaritmo algoritmo de percurso em pré-ordem. Esse algoritmo visita a raiz e então cada sub-árvore da esquerda a direita em uma maneira de percurso em pré-ordem. Em forma de pseudo-códigopseudocódigo, o algoritmo para pré-ordem é:

1. Visite a raiz de T. Ponha Coloque o atua atual vértice para ser a raiz.

Como pode ser visto no passo (2) do pseudo-código pseudocódigo acima, esse algoritmo é recursivo. Nós providenciamos a seguinte implementação em Maple:

A ordem em que nós percorremos os descendentes é determinada pela procedure booleana isLessThan (das seções anteriores). Para percorrer os descendentes em uma ordem diferente, use uma rotina de comparação de rotina diferente.Podemos examinar a execução esse procedure no percurso de árvore criado anteriormente, enraizado com raiz no vértice A.

Nós implementamos o percurso em ordem de maneira similar. Simplesmente alteramos a sequência na qual os vértices são visitados. Especificamente, olhamos na sub-árvore mais a à esquerda dos vértices, seguida pela raiz, e em seguida pela a sub-árvore mais a direita dos vértices. Em pseudo-códigopseudocódigo, temos:

1. Se a árvore T tem apenas um vérticer, r então visite r

2. Caso contrário, a árvore T tem mais que um vértice. Chame a sub-árvore mais a à esquerda(enraizada com raiz no filho mais a á esquerda) T_1. Percorre em ordem T_1, então visite a raiz r de T.

Determina Determine a ordem dos filhos e percorra a sub-árvore baseada no filho mais a à esquerda

Novamente, para percorrer os filhos em uma ordem diferente, use uma rotina de comparação de rotina diferentes diferente para ordenar os descendentes. Teste esse novo procedure executando ele em tree na árvore Trav.

O percurso final que devemos implementar implementaremos é em pós-ordem. Percurso O percurso em pós-ordem é similar ao percurso em pré-ordem, exceto que apenas visitamos a raiz após visitar cada sub-árvore. Segue o pseudo-códigopseudocódigo:

Também testamos esse procedure na tree árvore Trav com raiz A

Agora iremos discutir como usar o Maple para trabalhar com as formas infixa, pré-fixa e pós-fixa de expressões aritméticas. Essas formas são discutidas na sessão 8.33 do texto. Especificamente, iremos mostrar como criar uma representação em árvore binária de uma expressão infixa, como usar percursos em pós-ordem e pré-ordem para crias as formas pós-fixa e pré-fixa de expressões, respectivamente, e também como avaliar essas expressões a partir de suas formas pós-fixa e pré-fixa. Para começar essa seção, nós construímos um procedure em Maple que pega uma expressão aritmética infixa e a converte em um uma representação de árvore binária. Essa representação é em árvore binária pode ser percorrida usando os percursos das seções anteriores para formar vários formatos de representação aritmética. Como um exemplo, podemos construir uma árvore binária representando uma expressão infixa, como (3+10)^2 - (100-30)/(5*2), e então executar um percurso em pré-ordem nessa árvore para formar a representação pré-fixa dessa expressão aritmética.

No procedure em Maple que iremos implementearimplementar, consideraremos uma versão modificada da notação infixa, para evitar manipulações complicadas de string que depreciam o verdadeiro problema.

Dessa maneira, as facilidades de manipulação de lista do Maple ficam imediatamente disponíveis. Então, nós representamos expressões x + y as como [x,"+",y] , onde + é uma string.

O resultado é uma lista incluindo versões especialmente encodadas codificadas da string + , que não colide com usos anteriores de + como nome. (Cada vértice da expressão árvore deve ter um nome diferente, mesmo que eles pareçam iguais). 

Agora estamos prontos para construir uma árvore binária representando tal expressão. O algoritmo necessário para isso em pseudo-código pseudocódigo é:

2. Caso contrário, a lista consiste de um operando a à esquerda, um operador , e um operando a à direita. Use o algoritmo para construir a árvore binária para o operando a à esquerda.

3. Repita o passo (2) no operando a à direita.

Nossa implementação é a seguinteesta:

Se não tivermos sublistas em nossa expressão, retorne as listas de arestas e vértices como mostrado

A raiz da árvore é manipulada de maneira especial. Recomputando Recomputar a raiz da árvore é estranho complicado e carotaxativo, então nós simplesmente pedimos a cada árvore que se lembre de sua própria raiz. Isso é feito por declarações de tarefa como T(Root) := LocL;.

O procedure Unique é novamente usado para se assegurar que cada instancia de vértice tem nome único, mesmo que pareça igual a outro. Em todos os outros aspectos, a implementação é quase exatamente como descrito no pseudo-códigopseudocódigo.Para testar esse procedure, use-o para construir uma árvore de expressão árvore para a expressão anterior Expr1.

Suponha que somos dados uma representação em árvore binária de uma expressão aritmética. Nós podemos usar os algoritmos anteriormente criados para expressas essas árvores como expressões pós-fixas ou pré-fixas executando os percursos de pós-ordem ou pré-ordem, respectivamente. Como isso é trivial, cabe ao leitor explorar essa técnica.Como um exemplo final dessa seção, nós demonstramos como avaliar uma dada expressão pós-fixa. Para simplificar, nós representamos as operações básicas pelas primeiras letras das palavras add, subtract, multiply, divide e exponentiate. cabe Cabe ao leitor explorar como implementar um procedure que irá avaliar uma expressão pré-fixa, dado que essa técnica é a simples modificação do argumento que será usado no caso pós-fixo.

Note que em release 4, nós somos permitidos atribuir diretamente a à lista elements.

Para começar, nós iremos examinar a implementação do bubble sort. A razão pelo qual o bubble sort foi dado o nome "bubble" (bolha) é que o menor da lista "borbulha" em direção a frente da lista, se movendo um passo mais próximo a sua posições após cada iteração. O pseudo-códigopseudocódigo, que é destacado na página 575 do texto, é como o seguinte:

Nós iremos agora implementar o merge sort em Maple. Nós Usaremos também iremos usar o Maple para estudar a complexidade desse algoritmo. O algoritmo de merge sort pode ser implementado como um procedure recursivo. A idéia básica da tarefa de aplicar merge sort numa lista é de dividir a lista dividi-la em duas de tamanhos iguais ou quase iguais, ordenando cada sub-lista usando o algoritmo merge sort, e no final juntando as listas resultantes. Isso pode ser descrito no seguinte pseudo-códigopseudocódigo:

Agora nós damos o pseudo-código pseudocódigo para o algoritmo merge sort:

1. Se a lista L tem apenas um elemento, ela é está ordenada em ordem, então retornamos L como ela é.

Nós iremos agora analizar o tempo de execução do MergeSort em relação ao BubbleSort. Especificamente, nós iremos criar uma lista desordenada com 10000 1000 elementos aleatórios e executar o BubbleSort e o MergeSort nessa lista. Isso irá nos dar uma ilustração limitada do tempo de execução desses procedures, na qual o leitor deve expandir lendo análises teóricos no texto.

Para criar uma lista aleatória com 1000 100 elementos, usamos os comandos rand e seq do Maple, como representado a seguir:

O leitor é encorajado a implementar outros tipos de algoritmos de ordenação usando o Maple e a estudar a complexidade relativa desses algoritmos quando usandos para ordenar listas de vários tamanhos diferentes. Também é interessante usar técnicas de animação para ilustrar os passos dos algoritmos de ordenação. Apesar de não fazermos isso aqui, o leitor com habilidades avançadas de programação é convidado a fazê-lo. Tome nota especial para a Atente-se à importância de usar a estrutura de dados correta, ex: lists vs arrays.

Essa seção explica como usar o Maple para construir árvores de extensão (spanning trees) para grafos e como usar árvores de extensão usá-las para resolver muitos tipos diferentes de problema. Árvores de extensão já foram usadas no capítulo 7; elas tem uma grande quantidade de aplicações. Em particular, nós iremos mostrar como usar o Maple para formar as essas árvores de extensão usando dois algoritmos: depth-first search (busca em profundidade) e breadth-first search(busca em largura). Então nós iremos mostrar , mostraremos como usar o Maple para fazer backtracking, uma ténica baseada em depth-first search , usada para resolver vários problemas.

Para começar, nós iremos discutir discutiremos como implementar o algoritmo de depth-first search no Maple. Como o nome do algoritmo (busca em profundidade, em português) sugere, os vértices são visitados em ordem de crescimento crescente de profundidade da na árvore de extensão. O pseudo-código pseudocódigo é:

2. Escolha x para ser um vizinho de w que não está na árvore. Adicione aresta(x,w) e faça conjunto w igual a = x.

3. Repita o passo (2) até não haver ter mais vértices que não estão na árvore.

 Nós demonstramos Demonstramos o uso do procedure de depth-first search com o seguinte exemplo:

Tendo implementado o algoritmo de árvore de extensão de depth-first search, agora nós podemos modificar levemente o código Maple e conseguir uma árvore de extensão com breadth-first search. Especificamente, o O algoritmo de breadth-first search opera examinando todos os vértices da atual profundidade do grafo antes de se mover para baixo, no próximo nível do grafo. Antes de implementar esse algoritmo, nós damos uma descrição em pseudo-código do algoritmopseudocódigo dele.

2. Adicione arestas de V até para cada vértice em N_1 que ainda não está na árvore de extensão.

Note que as duas árvores de extensão são diferentes mesmo que elas estejam enraizadas tenham raiz no mesmo vértice. Em particular, a árvore com depth-first search tem uma estrutura funda e magra, enquanto a árvore com breadth-first search é menor e mais larga. Essas representações gráficas ajudam a ilustrar o algoritmo utilizado, e heuristicamente, nós podemos usar as representações para adivinhar qual dos dois algoritmos foi usado.

Click here to access a summary of all the Maple code used in this section.Backtracking é um método que pode ser usado para achar soluções para resolver problemas que poderiam ser impráticos de se resolver solucionar usando técnicas de busca excessiva, . O backtracking é baseado na busca sistemática pela solução de um problema usando uma árvore de decisão. Aqui nós mostramos comos como usar backtracking para reslver vários problemas diferentes, incluindo pintar um grafo, resolver o problema das n-rainhas de , que consiste em posicionar n rainhas em um tabuleiro de xadrez nXn de maneira que uma rainha não possa atacar a outra, e também o problema do subconjunto da soma, que consiste em visa encontrar um subconjunto de um conjunto de inteiros cuja soma é um inteiro dado inteiro.

O primeiro problemas problema que nós iremos atacar através de um procedure de backtracking é o de colorir um grafo usando n cores, onde sendo n é um inteiro positivo. Dado um grafo, nós tentaremos colorir ele usando n cores de uma maneira gananciosa. No entanto, quando nós atingimos uma coloração que não nos permite colorir um vértice adicional propriamente, nós usamos backtrack, mudando a cor de um vértice anteriormente colorido e tentando novamente. Aqui está o pseudo-código pseudocódigo para nosso procedure BackColor que executa essa coloração baseado em backtracking. Aqui nós ordenamos as cores como color1, color2, ..., colorn:

Uma implementação desse pseudo-código pseudocódigo no seguinte algoritmo Maple, chamado BackColor:

Outro problema que pode ser solucionado com uma solução elegante de backtracking é o problema de posicionar n-rainhas em um tabuleiro de xadrez de dimensão nXn de maneira que nenhuma rainha tem tenha como atacar a outra. Isso significa que nenhum par de rainhas pode ser posicionadona posicionado na mesma linha horizontal, vertical ou diagonal. Nós iremos resolver esse problema usando um procedure baseado em backtracking. Iremos posicionar as rainhas no tabuleiro de uma maneira gananciosa, até que todas as rainhas elas estejam posicionadas ou não haja mais posição disponível para um rainha ficar sem estar na mesma linha diagonal, vertical ou horizontal que outra já posicionada.