NQueens package

ملخص

تمثل مشكلة N-Queens تحديًا كلاسيكيًا في كثير من الأحيان في مقابلات البرمجة والإعدادات الأكاديمية. يكمن التحدي في وضع N Queens على لوحة شطرنج N × N بحيث لا يهدد ملكتان لبعضهما البعض. هذا يعني أنه لا يمكن لأي ملكات مشاركة نفس الصف أو العمود أو قطري.

بيان المشكلة

بالنظر إلى عدد صحيح n ، ارجع جميع الحلول المميزة إلى لغز N-Queens. يمكنك إعادة الإجابات بأي ترتيب.

يحتوي كل حل على تكوين لوح مميز لوضع N-Quins ، حيث يشير "Q" إلى ملكة و ".". يشير إلى مساحة فارغة.

مثال

بالنسبة إلى n = 4 ، الحلول الممكنة هي:

 [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

النهج والخوارزميات

خوارزمية التراجع

النهج الأكثر شيوعًا لحل مشكلة n-queens هو استخدام التراجع. تقوم خوارزمية التراجع ببناء المرشحين بشكل تدريجي إلى الحل وتتخلى عن المرشح بمجرد أن يحدد أن المرشح لا يمكن أن يؤدي إلى حل صالح.

خطوات:

1. Initialize the Board : ابدأ بلوحة N × N فارغة.
2. Place the Queen : حاول وضع الملكة في الصف الأول وانتقل إلى وضع الملكات اللاحقة.
3. Check Validity : لكل موضع ملكة ، تحقق مما إذا كان يتعارض مع الملكات الموضوعة بالفعل.
4. Backtrack if Necessary : إذا كان وضع الملكة يؤدي إلى أي حل ، فإزالة الملكة (التراكت) وجرب الموضع التالي.
5. Store the Solution : إذا تم العثور على تكوين صالح (N Queens الموضوعة) ، فقم بتخزين تكوين اللوحة.
6. Repeat : تابع هذه العملية حتى تتم تجربة جميع التكوينات الممكنة.

التحديات

تمثيل المجلس

يمكن تمثيل اللوحة باستخدام قائمة ثنائية الأبعاد حيث تكون كل خلية إما "Q" أو ".".

التحقق من النزاعات

من الأهمية بمكان التحقق من النزاعات: أمر بالغ الأهمية:

1. Row Check : التأكد من عدم وجود ملكات أخرى في نفس الصف.
2. Column Check : ضمان عدم وجود ملكات أخرى في نفس العمود.
3. Diagonal Check : ضمان عدم وجود ملكات أخرى على نفس القطر.

تحسين

يمكن أن يؤدي استخدام مجموعات لتتبع الأعمدة المحتلة والقطريات إلى تسريع عملية فحص الصراع.

التزامن مع threadpoolexecutor

لتحسين حل مشكلة N أكبر ، فإن الحل يعزز التزامن مع ThreadPoolexecutor:

• يبدأ كل مؤشر ترابط في حل المشكلة لعمود مختلف في الصف الأول.
• هذا النهج الموازي يمكن أن يقلل بشكل كبير من الوقت لإيجاد جميع الحلول.

حلنا

جاء هذا الحل Frome أحد تحديات الجمعة المجانية لدينا ، حيث نختار تحديات المقابلة العشوائية خلال فترة توقفنا لكتابة حلول لها.

تثبيت

 pip install wolfsoftware.NQueens

الاستخدام

 usage: nqueens [-h] [-v] [-V] [board_size]

See solutions to the NQueens problem.

positional arguments:
  board_size     Size of the board (default is 8 for the Eight Queens puzzle) (default: 8)

flags:
  -h, --help     Show this help message and exit
  -v, --verbose  Enable verbose output - show the actual boards (default: False)
  -V, --version  Show program's version number and exit.

The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

ملخص

تمثل مشكلة N-Queens تحديًا رائعًا ومعقدًا يتطلب فهمًا عميقًا للتكرار ، والتراجع ، وتقنيات التحسين. من خلال الاستفادة من متعدد الخيوط ، يجد هذا التنفيذ بكفاءة جميع الحلول الممكنة لحجم لوحة معين. يعد فهم وتنفيذ مشكلة N-Queens تمرينًا قيمًا لتحسين مهارات حل المشكلات والتفكير الخوارزمي.