Skip to content

Algoritmo que acha todas as soluções para qualquer valor de N no problema das N rainhas.

Notifications You must be signed in to change notification settings

Lacrymosaa/NQueenProblem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 

Repository files navigation

N Queen Problem

Algoritmo que acha todas as soluções para o problema das N rainhas, podendo N ser qualquer valor que apresente resultado. Embora o problema tenha sido apresentado a mim num contexto de algoritmos genéticos, onde me aprofundei nele através do mesmo contexto, este script usa o Backtracking.

O que é o Problema das N Rainhas?

"Este problema consiste em posicionar um número N de rainhas em um tabuleiro de xadrez de tamanho N*N de forma que nenhuma delas colida com a outra, considerando as regras de movimentação do jogo." - Citação do meu TCC "A Utilização de Algoritmos Genéticos na Otimização de Problemas"

O que é e como funciona o Backtracking?

Backtracking é um refinamento do algoritmo de busca por força bruta, que também pode ser descrito por enumeração exaustiva, no qual boa parte das soluções podem ser eliminadas sem serem explicitamente examinadas. De maneira simples, backtracking é uma estratégia recursiva de tentativa e erro, explorando diferentes caminhos para encontrar uma solução para um determinado problema. image
Imagem retirada de: https://www.simplilearn.com/tutorials/data-structure-tutorial/backtracking-algorithm

Referência do código

Utilizei este guia passo a passo como referência:: https://medium.com/cracking-the-coding-interview-in-ruby-python-and/8-12-the-8-queens-problem-with-solutions-ruby-javascript-and-python-409cea33b5b3 O problema com ele é que apenas apresenta as primeiras soluções encontradas por meio do backtracking. Por isso, fiz melhorias para que agora busque todas as soluções possíveis.

About

Algoritmo que acha todas as soluções para qualquer valor de N no problema das N rainhas.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages