Baru-baru ini saya melihat perkembangan / skrip lama saya dan menemukan skrip di mana masalah ratu terpecahkan. Sebenarnya, ini berfungsi untuk menulis artikel tentang bagaimana tahapan penulisan algoritmanya. Mungkin berguna bagi pemrogram pemula untuk memecahkan masalah serupa (kode dalam contoh ditulis dalam java).
pengantar
4 tahun yang lalu ada kehebohan tentang masalah penempatan 1000 ratu di papan berukuran 1000x1000. Faktanya adalah menempatkan ratu sehingga mereka tidak
satu sama lain di papan adalah masalah dengan sejumlah besar iterasi dan, akibatnya, waktu eksekusi yang lama. Seperti banyak orang lainnya, saya ingin memeriksa apakah ini dapat diselesaikan dalam waktu yang dapat diterima.
Pelajari tugasnya
Ada 8 ratu dalam gambar yang tidak berpotongan di sepanjang garis horizontal, vertikal atau diagonal.
Penting untuk menulis skrip yang akan menempatkan ratu di papan sesuai dengan aturan ini.
Algoritme untuk menemukan ratu
Rekursi dipilih untuk mencari bentuk.
Deskripsi metode yang memanggil dirinya sendiri:
Jika sel yang lewat berpotongan dengan gambar lain, maka kami kembali
false
Jika sel yang ditransfer tidak berpotongan dengan siapa pun:
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 .