وصف المشكلة: ضع ثماني ملكات على رقعة الشطرنج، ولا يمكن لملكتين مهاجمة بعضهما البعض (أي لا توجد ملكتان في نفس الصف أو العمود أو القطر) كما هو موضح في الصورة.
في هذه المقالة، يتم استخدام حلول مختلفة قليلاً للمشكلتين، لكن كلاهما يستخدم صفائف أحادية البعد. في الإصدار 6.20، كان من الضروري العثور على تخطيط فعال، حيث قمت بإنشاء مصفوفة مكونة من ثمانية عناصر عن طريق خلط قيم المصفوفة عشوائيًا ومقارنة القيمة بالنص المنخفض، وأخيرًا حصلت على تخطيط فعال 6.22، مطلوب البحث عن الكل تخطيط فعال، هنا أستخدم الأرقام الثمانية، واجتياز جميع الأرقام من 001234567-076543210، وتحويلها إلى سلاسل ثماني، ومقارنة كل بت بالمنخفض الخاص بها، وإخراج التخطيط الذي يلبي الشروط. سيتم عرض مبادئ وأساليب التنفيذ بالتفصيل أدناه.
الجزء 1 كيفية الحكم على ما إذا كان تخطيطًا صالحًا
نحن نتعامل مع رقعة الشطرنج على أنها مصفوفة 8*8، تتراوح من 0 إلى 7. وبملاحظة الصورة على اليسار تجد أن تخطيطها يمكن تمثيله بمجموعة من أزواج الأرقام (من الأعلى إلى الأسفل)، وهي (0، 0)، (1، 6)، (2، 3)، (3) ، 5)، (4، 7)، (5، 1)، (6، 4)، (7، 2). ممثلة بمصفوفة، أي int []list = {0, 6, 3, 5, 7, 1, 4, 2};
من الواضح أن هذا تخطيط صالح. بعد ذلك علينا أن نفكر في سؤال: في التخطيط الفعال، هل هناك أي علاقة بين الحرف المنخفض والقيمة المقابلة له في المصفوفة، أي i وlist[i]؟
قمنا هنا بتعيين list[i] = k; list[j] = q (i > j) الذي يستوفي الشرطين التاليين (يسهل فهمه عند الرسم على الورق):
1.ك != س;
2. i - j == k - q أو i - j == q -k (تم الحصول عليه من السؤال)
من أجل التأكد من أن k != q، تم الإعلان عن قائمة المصفوفات وتهيئتها هنا بحيث تكون list[i] = i. ثم قم بتبديل المصفوفة بشكل عشوائي، ثم تحقق من استيفاء الشرط 2
انسخ رمز الكود كما يلي:
// إنشاء المصفوفة وتهيئتها
int [] list = new int [arrSize];
ل(int i = 0; i < arrSize; i++)
قائمة[i] = i;
// قم بخلط المصفوفة بشكل عشوائي
public static void RanmizeArray(int [] list){
int arrSize = list.length;
int ranIndex;
for(int i = 0; i < arrSize; i++){
ranIndex = (int)(Math.random() * arrSize);
إذا (رانإندكس!= أنا){
int temp = list[i];
list[i] = list[ranIndex];
list[ranIndex] = temp;
}
}
}
نص الكود 6.20 هو كما يلي
انسخ رمز الكود كما يلي:
// 6.20 لعبة: ثماني ملكات
الفراغ العام SolEightQueens () {
int arrSize = 8;
int [] list = new int [arrSize];
ل(int i = 0; i < arrSize; i++)
قائمة[i] = i;
عدد صحيح = 0؛
boolean notValid = true;
بينما (غير صالح) {
العد++;
notValid = false;
RandomizeArray(list);
for(int i = 0; i < arrSize; i++){
for(int j = i + 1; j < arrSize; j++){
if(j - i == Math.abs(list[j] - list[i])){ // التحقق من استيفاء الشرط
notValid = true;
استراحة؛
}
}
إذا (غير صالح) استراحة؛
} // نهاية الحلقة الخارجية
} // نهاية الوقت
// اطبع النتيجة
كثافة العمليات أنا؛
System.out.println("O(∩_∩)Ohaha~، لقد حاولت " + count + " مرات، ونجحت في النهاية.");
ل(i = 0; i < arrSize - 1; i++){
System.out.print("(" + i + ", " + list[i] + "), ");
}
System.out.println("(" + i + ", " + list[i] + ")");
}
الجزء 2 البحث عن جميع التخطيطات الصالحة
نظرًا لأن الإصدار 6.22 يتطلب العثور على جميع تخطيطات الملكات الثمانية الصالحة، فإن طريقة خلط المصفوفة عشوائيًا لم تعد قابلة للتطبيق، لذا يتعين علينا العثور على طريقة يمكنها اجتياز جميع المصفوفات الممكنة. إحدى الطرق الأكثر مباشرة هي استخدام حلقة مكونة من ثماني طبقات، ولكن كمية التعليمات البرمجية كبيرة جدًا ومن السهل إغماء الرأس، لذلك لا يتم استخدام هذه الطريقة.
من خلال مراقبة قيم المصفوفة بعناية في الجزء الأول، يمكنك أن تجد أنها كلها تتراوح بين 0-7، لذا فإن الاجتياز باستخدام أرقام int الثماني يمكن أن يضمن تضمين كل التقليب. نظرًا لأن الأرقام المكونة من ثمانية أرقام مختلفة، فهناك 8 = 40320 تبديلًا محتملاً، والعدد الإجمالي للأرقام الثمانية هو 8^8 = 16777216، وبالتالي فإن النسبة المحتملة تمثل 40320/16777216 = 1/416، مما يؤدي إلى 40320. التباديل هناك أيضًا عمليات فحص لتصفية التصميم النهائي الصالح. لا تزال هذه الطريقة غير فعالة بعض الشيء، لكنني لم أكتشف طريقة أكثر كفاءة بعد.
انسخ رمز الكود كما يلي:
// 6.22 اللعبة: حلول مختلفة لمسألة الملكات الثمانية (زيادة قيمة int، ثم تحويلها إلى سلسلة ثماني، ثم التحقق منها)
حل الفراغ الثابت العامEightQueensMethod(){
int start = 001234567;
int end = 076543210;
int count = 0; // احسب عدد التخطيطات الصالحة
for(int i = start; i < end; i++){
boolean isValid = isValid(i);
إذا (صالح) {
إذا (++ عدد % 7 == 0)
System.out.println(Integer.toOctalString(i) + ": " + isValid);
else System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
}
}
System.out.println("count = "+count); // إخراج عدد التخطيطات الصالحة
}
// تحقق مما إذا كان الرقم تخطيطًا صالحًا
المنطق المنطقي العام الثابت صالح (رقم int) {
String numOct = Integer.toOctalString(number);
int arrSize = numOct. length();
if(arrSize==7) { // إذا كان الرقم الأول من الرقم هو 0، فإن السلسلة التي تم إنشاؤها تحتوي على سبعة أحرف فقط
numOct = '0' + numOct;
arrSize++;
}
for(int i = 1; i < arrSize; i ++){
ل(int j = i - 1; j >= 0; j--){
if(numOct.charAt(i) == numOct.charAt(j)) يُرجع خطأ // نفس العمود
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) return false;
}
}
عودة صحيحة؛
}
ملحق الجزء الثالث: مشكلة توليد المجموعات
كان هناك مثل هذا السؤال في اختبار كتابي العام الماضي. نظرا للتسلسل، إخراج كافة المجموعات. على سبيل المثال،
مخرجات "123": 1، 2، 3، 12، 13، 21، 23، 31، 32، 123، 132، 213، 231، 312، 321
إخراج "abcd": a، b، c، d، ab، ac، ad، ba، bc، bd، ca، cb، cd، da، db، dc، abc، acb، abd، adb، acd، adc، ...، اي بي سي، ...
في الإصدار 6.22، الطريقة المستخدمة للعثور على جميع تخطيطات الملكات الثمانية هي زيادة رقم النوع int ثم التحقق واحدًا تلو الآخر. يمكن حل المشكلة المذكورة أعلاه بطريقة مماثلة. ومع ذلك، فإن الكفاءة منخفضة بعض الشيء. إذا كانت هناك طريقة أكثر كفاءة، فيرجى طلب التوجيه من أحد الخبراء.