Uraian masalah: Tempatkan delapan ratu di papan catur. Tidak ada dua ratu yang dapat saling menyerang (yaitu, tidak ada dua ratu yang berada pada baris, kolom, atau diagonal yang sama) seperti yang ditunjukkan pada gambar.
Dalam artikel ini, solusi yang sedikit berbeda digunakan untuk kedua masalah tersebut, tetapi keduanya menggunakan array satu dimensi. Di 6.20, diperlukan untuk menemukan tata letak yang efektif. Saya membuat array satu bit dengan delapan elemen. Dengan mengacak nilai array secara acak, dan membandingkan nilainya dengan subskrip, saya akhirnya mendapatkan tata letak yang efektif; 6.22, diperlukan Temukan semua Tata letak yang efektif, disini saya menggunakan bilangan oktal, melintasi semua bilangan dari 001234567-076543210, mengubahnya menjadi string oktal, membandingkan setiap bit dengan subskripnya, dan menampilkan tata letak yang memenuhi syarat. Prinsip dan metode implementasi akan diperkenalkan secara rinci di bawah ini.
Bagian 1 Bagaimana menilai apakah tata letaknya valid
Kami memperlakukan papan catur sebagai matriks 8*8, berkisar antara 0-7. Perhatikan gambar sebelah kiri, terlihat bahwa tata letaknya dapat diwakili oleh sekumpulan pasangan bilangan (dari atas ke bawah), yaitu (0, 0), (1, 6), (2, 3), (3 , 5), (4, 7), (5, 1), (6, 4), (7, 2). Diwakili oleh sebuah array, yaitu int []list = {0, 6, 3, 5, 7, 1, 4, 2};
Jelas, ini adalah tata letak yang valid. Selanjutnya kita harus mempertimbangkan sebuah pertanyaan: Dalam tata letak yang efektif, apakah ada hubungan antara subskrip dan nilai terkaitnya dalam array, yaitu i dan list[i]?
Di sini kita menetapkan list[i] = k; list[j] = q; (i > j), yang memenuhi dua kondisi berikut (lebih mudah dipahami jika digambar di atas kertas):
1. k != q;
2. i - j == k - q atau i - j == q -k (diperoleh dari soal)
Untuk memastikan bahwa k != q, daftar array dideklarasikan dan diinisialisasi di sini sehingga daftar[i] = i. Kemudian acak arraynya, lalu periksa apakah kondisi 2 terpenuhi
Copy kode kodenya sebagai berikut:
// Membuat dan menginisialisasi array
int [] daftar = int baru [arrSize];
untuk(int i = 0; i < arrSize; i++)
daftar[i] = saya;
// Mengacak array secara acak
public static void randomizeArray(int [] daftar){
int arrSize = daftar.panjang;
int indeks acak;
untuk(int i = 0; i < arrSize; i++){
ranIndex = (int)(Matematika.random() * arrSize);
jika(ranIndex != i){
int suhu = daftar[i];
daftar[i] = daftar[ranIndex];
daftar[ranIndex] = suhu;
}
}
}
Badan kode 6.20 adalah sebagai berikut
Copy kode kodenya sebagai berikut:
// 6.20 Permainan: Delapan Ratu
public void solveEightQueens(){
int arrUkuran = 8;
int [] daftar = int baru [arrSize];
untuk(int i = 0; i < arrSize; i++)
daftar[i] = saya;
int hitungan = 0;
boolean notValid = benar;
while(tidakValid){
hitungan++;
tidak valid = salah;
randomizeArray(daftar);
untuk(int i = 0; i < arrSize; i++){
untuk(int j = i + 1; j < arrUkuran; j++){
if(j - i == Math.abs(list[j] - list[i])){ // Periksa apakah kondisi terpenuhi
tidakValid = benar;
merusak;
}
}
if(notValid) rusak;
} // akhir perulangan for bagian luar
} // akhir sementara
// cetak hasilnya
ke dalam aku;
System.out.println("O(∩_∩)Ohaha~, saya sudah mencoba " + count + " kali, dan akhirnya berhasil.");
untuk(i = 0; i < arrUkuran - 1; i++){
System.out.print("(" + i + ", " + daftar[i] + "), ");
}
System.out.println("(" + i + ", " + daftar[i] + ")");
}
Bagian 2 Temukan semua tata letak yang valid
Karena 6.22 memerlukan pencarian semua tata letak delapan ratu yang valid, metode pengacakan larik secara acak tidak lagi berlaku, jadi kita harus menemukan metode yang dapat melintasi semua kemungkinan larik. Salah satu metode yang paling langsung adalah dengan menggunakan perulangan for delapan lapis, tetapi jumlah kodenya terlalu besar dan head mudah pingsan, sehingga metode ini tidak digunakan.
Dengan mengamati dengan cermat nilai array di Bagian 1, Anda akan menemukan bahwa semuanya berada di antara 0-7, jadi penelusuran menggunakan angka int oktal dapat memastikan bahwa setiap permutasi disertakan. Karena bilangan delapan digitnya berbeda, maka ada 8! = 40320 kemungkinan permutasi, dan jumlah bilangan oktalnya adalah 8^8 = 16777216, jadi rasio yang mungkin adalah 40320/16777216 = 1/416, sehingga menghasilkan 40320. permutasi Ada juga pemeriksaan untuk menyaring tata letak akhir yang valid. Cara ini masih agak kurang efisien, namun saya belum menemukan cara yang lebih efisien.
Copy kode kodenya sebagai berikut:
// 6.22 Game: Berbagai solusi untuk masalah delapan ratu (menambah nilai int, lalu mengubahnya menjadi string oktal, lalu memeriksa)
public static void solveEightQueensMethod(){
int mulai = 001234567; // Oktal
int akhir = 076543210; // oktal
int count = 0; // Hitung jumlah layout yang valid
untuk(int i = mulai; saya < akhir; i++){
boolean isValid = isValid(i);
jika(adalahValid){
jika(++hitung % 7 == 0)
System.out.println(Integer.toOctalString(i) + ": " + isValid);
else System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
}
}
System.out.println("count = " + count); // Menampilkan jumlah layout yang valid
}
// Periksa apakah nomor adalah tata letak yang valid
boolean statis publik isValid(int angka){
String numOct = Integer.toOctalString(angka);
int arrSize = numOct.length();
if(arrSize==7) { // Jika digit pertama angka adalah 0, string yang dihasilkan hanya memiliki tujuh karakter
angkaOktober = '0' + angkaOktober;
arrUkuran++;
}
untuk(int i = 1; i < arrUkuran; i ++){
untuk(int j = i - 1; j >= 0; j--){
if(numOct.charAt(i) == numOct.charAt(j)) mengembalikan false; // kolom yang sama
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) mengembalikan false;
}
}
kembali benar;
}
Bagian 3 Ekstensi: Masalah menghasilkan kombinasi
Ada pertanyaan seperti itu dalam tes tertulis tahun lalu. Jika diberi urutan, keluarkan semua kombinasi. Misalnya,
Keluaran "123": 1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321
Keluaran "abcd": a, b, c, d, ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc, abc, acb, abd, adb, acd, adc, ..., abcd, ...
Di 6.22, metode yang digunakan untuk menemukan semua tata letak delapan ratu adalah dengan menambah nomor tipe int dan kemudian memeriksa satu per satu. Masalah di atas dapat diselesaikan dengan cara serupa. Namun efisiensinya agak rendah. Jika ada cara yang lebih efisien, silakan minta petunjuk pada ahlinya.