Recentemente, eu estava examinando meus desenvolvimentos / scripts antigos e me deparei com um script onde o problema das rainhas foi resolvido. Na verdade, isso serviu para escrever um artigo sobre como foram as etapas de escrita de seu algoritmo. Talvez seja útil para programadores novatos para resolver problemas semelhantes (o código nos exemplos é escrito em java).
Introdução
4 anos atrás, houve um rebuliço sobre o problema de colocar 1000 damas em um tabuleiro de 1000x1000. O fato é que colocar rainhas de modo que não sejam
umas às outras no tabuleiro é um problema com um grande número de iterações e, como resultado, um longo tempo de execução. Como muitos outros, eu queria verificar se isso poderia ser resolvido em um prazo aceitável.
Estude a tarefa
Existem 8 rainhas na imagem que não se cruzam ao longo de linhas horizontais, verticais ou diagonais.
É necessário escrever um roteiro que colocará as rainhas no tabuleiro de acordo com essas regras.
Algoritmo para encontrar rainhas
A recursão foi escolhida para pesquisar formas.
Descrição do método que chama a si mesmo:
Se a célula passada cruzar com outras figuras, então retornamos
false
Se a célula transferida não se cruzar com ninguém:
true
.
( )
true
.
.
false
false
)false
.
true
.
8x8, 32x32, 50x50 . .
.
.
.
. .
.
400x400.
.
.
.
.
.
"row+1" "column+2" , .
1000x1000 ~4 ( : Intel Core i5-10400H CPU 2.60GHz).
1116x1116 ~6 .