Récemment, je regardais mes anciens développements / scripts et suis tombé sur un script où le problème des reines a été résolu. En fait, cela a servi à écrire un article sur la façon dont les étapes d'écriture de son algorithme se sont déroulées. Peut-être utile pour les programmeurs novices pour résoudre des problèmes similaires (le code des exemples est écrit en java).
introduction
Il y a 4 ans, le problème du placement de 1000 reines sur une planche de 1000x1000 a fait sensation. Le fait est que placer des reines de manière à ce qu'elles ne soient pas les
unes les autres sur le plateau est un problème avec un grand nombre d'itérations et, par conséquent, un temps d'exécution long. Comme beaucoup d'autres, je voulais vérifier si cela pouvait être résolu dans un délai acceptable.
Étudiez la tâche
Il y a 8 reines dans l'image qui ne se croisent pas le long de lignes horizontales, verticales ou diagonales.
Il est nécessaire d'écrire un script qui placera les reines sur le plateau selon ces règles.
Algorithme pour trouver des reines
La récursivité a été choisie pour rechercher des formes.
Description de la méthode qui s'appelle:
Si la cellule passée croise d'autres chiffres, nous retournons
false
Si la cellule transférée ne croise personne:
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 .