Kürzlich habe ich mich mit meinen alten Entwicklungen / Skripten befasst und bin auf ein Skript gestoßen, in dem das Problem der Königinnen gelöst wurde. Tatsächlich diente dies dazu, einen Artikel darüber zu schreiben, wie die Phasen des Schreibens seines Algorithmus abliefen. Vielleicht nützlich für unerfahrene Programmierer, um ähnliche Probleme zu lösen (der Code in den Beispielen ist in Java geschrieben).
Einführung
Vor 4 Jahren gab es Aufsehen über das Problem, 1000 Königinnen auf einem 1000x1000-Brett zu platzieren. Tatsache ist, dass das Platzieren von Königinnen so, dass sie sich nicht
gegenseitig auf dem Brett sind, ein Problem mit einer großen Anzahl von Iterationen und infolgedessen einer langen Ausführungszeit ist. Wie viele andere wollte ich prüfen, ob es in einer akzeptablen Zeit gelöst werden kann.
Studiere die Aufgabe
Das Bild enthält 8 Königinnen, die sich nicht entlang horizontaler, vertikaler oder diagonaler Linien schneiden.
Es ist notwendig, ein Skript zu schreiben, das Königinnen gemäß diesen Regeln auf dem Brett platziert.
Algorithmus zum Finden von Königinnen
Die Rekursion wurde gewählt, um nach Formen zu suchen.
Beschreibung der Methode, die sich selbst aufruft:
Wenn sich die übergebene Zelle mit anderen Figuren schneidet, kehren wir zurück
false
Wenn sich die übertragene Zelle mit niemandem schneidet:
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 .