Mengenai solusi JavaScript untuk masalah delapan ratu, saya selalu merasa bahwa saya perlu mempelajari algoritma. Akan memalukan untuk mengetahui apakah saya menggunakannya suatu hari nanti.
latar belakang
Pertanyaan delapan ratu adalah pertanyaan yang didasarkan pada catur: Bagaimana delapan ratu dapat ditempatkan di papan catur 8 × 8 sehingga tidak ada ratu yang bisa memakan ratu lainnya secara langsung? Untuk mencapai hal ini, tidak ada ratu yang berada dalam garis horizontal, vertikal atau diagonal yang sama
Masalah delapan ratu dapat digeneralisasi ke masalah penempatan N Queen yang lebih umum: pada saat ini ukuran papan catur menjadi n × n, dan jumlah ratu juga menjadi n. Jika dan hanya jika n = 1 atau n ≥ 4 ada solusi untuk masalah
Algoritma enumerasi buta
Melalui N-Fold Loop, menyebutkan solusi yang memenuhi kendala (ada banyak kode loop delapan kali lipat, loop empat kali lipat dilakukan di sini), temukan semua posisi yang mungkin dari keempat ratu, dan kemudian menilai di seluruh papan apakah keempat ratu ini akan saling memakan secara langsung. Gagasan program relatif sederhana.
function check1 (arr, n) {for (var i = 0; i <n; i ++) {for (var j = i+1; j <n; j ++) {if ((arr [i] == arr [j]) || math.abs (arr [i] - arr [j]) == j - i) {return false; }}} return true;} function queen1 () {var arr = []; untuk (arr [0] = 1; arr [0] <= 4; arr [0] ++) {for (arr [1] = 1; arr [1] <= 4; arr [1] ++) {for (arr [2] = 1; arr [2] <= 4; arr [2] ++) {untuk (arr [3] = 1; arr [ARR 3] <= 4; ARR [2] ++) {for (arr [3] = 1; arr [arr [3] <= 4; melanjutkan; } else {console.log (arr); }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}Mengenai hasilnya, di papan catur 4*4, keempat ratu tidak dapat berturut -turut. ARR [0] ke ARR [3] masing -masing berhubungan dengan empat ratu. Nilai yang sesuai dengan subskrip array dan subskrip adalah posisi ratu di papan tulis.
Metode backtracking
"Jika kamu tidak bisa pergi, berbalik saja." Tentukan apakah itu mencocokkannya di simpul yang sesuai. Jika tidak cocok, Anda tidak akan lagi menjelajahi cabang ini.
function check2 (arr, n) {for (var i = 0; i <= n - 1; i ++) {if ((math.abs (arr [i] - arr [n]) == n - i) || (arr [i] == arr [n])) {return false; }} return true;} function queen2 () {var arr = []; untuk (arr [0] = 1; arr [0] <= 4; arr [0] ++) {for (arr [1] = 1; arr [1] <= 4; arr [1] ++) {if (! check2 (arr, 1)) lanjutkan; // Nyatakan konflik antara dua ratu untuk (arr [2] = 1; arr [2] <= 4; arr [2] ++) {if (! Check2 (arr, 2)) lanjutkan; // Nyatakan konflik antara tiga ratu untuk (arr [3] = 1; arr [3] <= 4; arr [3] ++) {if (! Check2 (arr, 3)) {lanjutkan; } else {console.log (arr); }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} }}}}}}}}}}}}}}Backtracking non-rekursif
Kerangka Algoritma:
sementara (k> 0 『Ada cara untuk pergi』 dan 『tidak mencapai tujuan』) {// k> 0 『Ada cara untuk pergi jika (k> n) {// Cari node daun // Cari solusi, output} lain {// a [k] Nilai pertama saat (" a [k] ada di ruang pencarian ") {/ a [k] Nilai pertama saat (" a [k] ada di ruang pencarian ") {a [k] ruang pencarian ") {// tandai sumber daya yang ditempati // k = k + 1; } else {// Bersihkan ruang keadaan yang ditempati // k = k - 1; }}}Kode spesifiknya adalah sebagai berikut. Lapisan terluar sementara berisi dua bagian. Salah satunya adalah traversal dari nilai -nilai ratu saat ini yang mungkin, dan yang lainnya adalah keputusan apakah akan memasukkan lapisan berikutnya atau mundur lapisan sebelumnya.
function backdate (n) {var arr = []; var k = 1; // Arr ratu ke -n [0] = 1; while (k> 0) {arr [k-1] = arr [k-1] + 1; while ((arr [k-1] <= n) && (! check2 (arr, k-1))) {arr [k-1] = arr [k-1] + 1; } // ratu ini memenuhi kendala dan membuat penilaian berikutnya jika (arr [k-1] <= n) {if (k == n) {// console ratu ke-n (arr); } else {k = k + 1; // ratu arr berikutnya [k-1] = 0; }} else {k = k - 1; // backtrack, ratu terakhir}}} backdate (4); // [2, 4, 1, 3] // [3, 1, 4, 2]Metode backtracking rekursif
Panggilan rekursif sangat mengurangi jumlah kode dan meningkatkan keterbacaan program.
var arr = [], n = 4; fungsi backtrack (k) {if (k> n) {console.log (arr); } else {for (var i = 1; i <= n; i ++) {arr [k-1] = i; if (check2 (arr, k-1)) {backtrack (k + 1); }}}}} backtrack (1); // [2, 4, 1, 3] // [3, 1, 4, 2]Amb cantik
Apa itu Amb? Berikan daftar data, yang dapat mengembalikan cara untuk memenuhi situasi keberhasilan kendala. Tanpa berhasil, itu akan gagal. Tentu saja, itu dapat mengembalikan semua situasi sukses. Penulis telah menulis begitu banyak poin di atas, hanya untuk merekomendasikan algoritma AMB ini di sini. Sangat cocok untuk menangani skenario backtracking sederhana. Ini sangat menarik. Mari kita lihat cara kerjanya.
Pertama, mari kita berurusan dengan masalah kecil, temukan string yang berdekatan: dapatkan beberapa set array string, dan setiap array mengeluarkan string. Karakter terakhir dari string sebelumnya sama dengan karakter pertama dari string berikutnya. Jika kondisinya terpenuhi, string yang baru diambil akan menjadi output.
Ambrun (function (amb, fail) {// Metode kendala Fungsi ditautkan (s1, s2) {return s1.slice (-1) == s2.slice (0, 1);} // suntikan daftar data var w1 = aMB (["itu", "itu", "]; "TREEDE" Grows "]);Ini terlihat sangat sederhana atau tidak! Namun, premis penggunaan adalah bahwa Anda tidak peduli dengan kinerja, itu benar -benar buang -buang waktu!
Di bawah ini adalah implementasi JavaScript. Jika Anda tertarik, Anda dapat mempelajari cara mengekstrak backtracking.
fungsi Ambrun (func) {var choices = []; indeks var; fungsi amb (values) {if (values.length == 0) {fail (); } if (index == choices.length) {choices.push ({i: 0, count: values.length}); } var choice = pilihan [index ++]; nilai pengembalian [pilihan.i]; } function fail () {throw fail; } while (true) {coba {index = 0; return func (Amb, fail); } catch (e) {if (e! = fail) {throw e; } var choice; while ((choice = choices.pop ()) && ++ choice.i == choice.count) {} if (choice == tidak terdefinisi) {return tidak terdefinisi; } pilihan.push (pilihan); }}}Dan kode spesifik dari masalah delapan ratu yang diimplementasikan menggunakan Amb
Ambrun (function (amb, fail) {var n = 4; var arr = []; var turn = []; for (var n = 0; n <n; n ++) {turn [turn.length] = n +1;} sementara (n--) {arr. var a = arr [i], b = arr [j];Solusi javascript untuk masalah delapan ratu
Ini adalah solusi JavaScript untuk masalah delapan ratu. Seluruh program tidak digunakan untuk loop, dan diimplementasikan melalui rekursi. Ini sepenuhnya memanfaatkan peta, mengurangi, menyaring, concat, irisan metode objek array.
'Gunakan ketat'; var queens = function (boarderSize) {// Gunakan rekursi untuk menghasilkan interval array var dari awal ke akhir = fungsi (start, end) {if (start> end) {return []; } return interval (start, end - 1) .concat (end); }; // Periksa apakah kombinasi valid var isValid = fungsi (queencol) {// periksa apakah ada konflik antara dua posisi var isafe = fungsi (pointa, pointb) {var slope = (pointa.row - pointb.row) / (pointa.col - pointb.col); if ((0 === slope) || (1 === Slope) || (-1 === Slope)) {return false; } return true; }; var len = queencol.length; var pointtocompare = {row: queencol [len - 1], col: len}; // Pertama -tama iris array kecuali kolom terakhir, lalu uji apakah ada konflik antara titik -titik di setiap kolom dan titik yang akan diuji, dan akhirnya menggabungkan hasil tes. Return queencol .slice (0, len - 1) .map (function (baris, indeks) {return isSafe ({row: row, col: index + 1}, pointtocompare);}) .reduce (function (a, b) {return a && b;}); }; // Rekursif menghasilkan kombinasi yang sesuai dengan aturan var queencols = fungsi (ukuran) {if (1 === ukuran) {return interval (1, boardersize) .map (function (i) {return [i];}); } // Pertama memperluas set semua kolom sebelumnya yang sesuai dengan aturan, kemudian gunakan pengurangan pengurangan dimensi, dan akhirnya gunakan isValid untuk menyaring kombinasi yang sesuai dengan aturan pengembalian queencol (ukuran - 1) .map (function) {queencol) {return interval (1, boarderSize) .map (function (row) {queencol) {return interval (1, boarderSize) .map (function (row) {queencol) {return interval (1, boarderSize) .map (function (row) {queencol) {retruce queenc (Conate). (a, b) {return a.concat (b);}) .filter (isValid); }; // ratu fungsi entri pengembalian queencols (boarderSize);}; console.log (queens (8)); // hasil output: // [[1, 5, 8, 6, 3, 7, 2, 4], // [1, 6, 8, 3, 7, 4, 2, 5], // ... // [8, 3, 3, 8, 8, 7, 4, 2, 5],// // [8, 3, 3, 1, 1, 4, 4, 4, 2],/ // [8, 6, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 2, 7, 5]]PS: Masalah Extended N Queen
Ketika pemain catur Max Bezzel bertanya pada teka -teki delapan ratu pada tahun 1848, ia mungkin tidak pernah berpikir bahwa lebih dari 100 tahun kemudian, masalah ini menjadi salah satu kursus wajib terpenting dalam pembelajaran pemrograman. Masalah delapan ratu terdengar sangat sederhana: menempatkan delapan ratu di papan catur sehingga delapan ratu tidak saling menyerang (papan catur adalah array persegi 8 × 8, dan ratu dapat mengambil beberapa langkah dalam delapan arah secara horizontal dan vertikal). Meskipun ada 92 solusi untuk masalah ini, tidak mudah untuk menemukan satu solusi dengan tangan kosong. Angka berikut adalah salah satu solusi:
Ada banyak varian dari masalah delapan ratu, tetapi tidak peduli seberapa keras itu, itu tidak akan lebih tampan daripada varian berikut: tolong rancang rencana untuk menempatkan ratu di setiap baris dan setiap kolom papan catur yang tak terbatas, sehingga semua ratu tidak saling menyerang. Secara khusus, anggaplah sudut kiri bawah papan ini berasal dari asalnya, dengan barisan tak terbatas dari bawah ke atas dan kolom tak terbatas dari kiri ke kanan, Anda perlu mencari tahu pengaturan semua bilangan bulat positif A1, A2, A3, ... sehingga ketika Anda menempatkan ratu pertama di baris pertama di kolom A1, ratu kedua di kolom A2, dll. Tidak ada dua ratu.
Berikut ini adalah konstruksi yang sangat sederhana dan pintar. Pertama, kami memberikan jawaban untuk masalah lima ratu. Dan yang sangat penting, salah satu ratu menempati jaringan di sudut kiri bawah.
Selanjutnya, kami memperluas solusi dari lima ratu ke 25 ratu, dan berdasarkan tata letak lima ratu itu sendiri:
Akibatnya, lima ratu dalam kelompok yang sama jelas tidak akan saling menyerang, dan ratu dalam kelompok yang berbeda jelas tidak akan saling menyerang. Ini adalah solusi 25 ratu yang memenuhi persyaratan. Perhatikan bahwa setelah ekspansi, bagian yang sebelumnya diisi belum berubah.
Apa yang harus saya lakukan selanjutnya? Itu benar, kami menyalin 25 ratu tanpa blok menjadi lima bagian, dan mengaturnya lagi sesuai dengan tata letak lima ratu, sehingga berkembang menjadi 125 ratu!
Dengan terus berkembang ke luar berdasarkan bagian -bagian yang diisi seperti ini, Anda dapat menghasilkan solusi untuk masalah ratu yang tak terbatas.