مسألة الملكات n

كما يوضح الشكل أدناه، عندما $n = 4$، يوجد حلان يمكن إيجادهما. ومن منظور خوارزمية التتبّع الرجعي، تحتوي رقعة الشطرنج $n \times n$ على $n^2$ مربعاً، وهذه المربعات توفر جميع الخيارات choices. وخلال عملية وضع الملكات واحدة تلو الأخرى، تتغير حالة رقعة الشطرنج باستمرار، وتمثل رقعة الشطرنج في كل لحظة الحالة state.

ويوضح الشكل أدناه القيود الثلاثة لهذه المسألة: لا يمكن لعدة ملكات أن تكون في الصف نفسه أو العمود نفسه أو على القطر نفسه. ومن الجدير بالذكر أن الأقطار تنقسم إلى نوعين: القطر الرئيسي \ والقطر المضاد /.

استراتيجية الوضع صفاً بصف

بما أن عدد الملكات وعدد صفوف رقعة الشطرنج كلاهما $n$، يمكننا استنتاج نتيجة بسهولة: يسمح كل صف في رقعة الشطرنج بوضع ملكة واحدة فقط لا غير.

وهذا يعني أنه يمكننا اعتماد استراتيجية الوضع صفاً بصف: بدءاً من الصف الأول، نضع ملكة واحدة في كل صف حتى يكتمل الصف الأخير.

ويوضح الشكل أدناه عملية الوضع صفاً بصف لمسألة 4 ملكات. ونظراً لضيق المساحة، لا يوسّع الشكل إلا فرع بحث واحد من الصف الأول، وتُشذَّب جميع المخططات التي تخالف قيد العمود أو القطر.

في جوهر الأمر، تؤدي استراتيجية الوضع صفاً بصف وظيفة التشذيب، إذ تتجنب جميع فروع البحث التي تظهر فيها عدة ملكات في الصف نفسه.

تشذيب الأعمدة والأقطار

لتحقيق قيد العمود، يمكننا استخدام مصفوفة منطقية cols بطول $n$ لتسجيل ما إذا كان في كل عمود ملكة. وقبل كل قرار وضع، نستخدم cols لتشذيب الأعمدة التي تحتوي بالفعل على ملكات، ونحدّث حالة cols ديناميكياً أثناء التتبّع الرجعي.

فكيف نتعامل مع قيد القطر؟ لنأخذ مربعاً في رقعة الشطرنج بفهرسي صف وعمود $(row, col)$. إذا اخترنا قطراً رئيسياً محدداً في المصفوفة، نجد أن جميع المربعات على ذلك القطر لها الفرق نفسه بين فهرسي الصف والعمود، أي أن $row - col$ قيمة ثابتة لجميع المربعات على القطر الرئيسي.

وبعبارة أخرى، إذا حقق مربعان $row_1 - col_1 = row_2 - col_2$، فلا بد أنهما على القطر الرئيسي نفسه. وباستخدام هذا النمط، يمكننا استخدام المصفوفة diags1 الموضحة في الشكل أدناه لتسجيل ما إذا كانت هناك ملكة على كل قطر رئيسي.

وبالمثل، بالنسبة إلى جميع المربعات على قطر مضاد، يكون المجموع $row + col$ قيمة ثابتة. ويمكننا بالمثل استخدام المصفوفة diags2 للتعامل مع قيود الأقطار المضادة.

تنفيذ الشيفرة

يرجى ملاحظة أنه في مصفوفة مربعة $n \times n$، يكون نطاق $row - col$ هو $[-n + 1, n - 1]$، ونطاق $row + col$ هو $[0, 2n - 2]$. لذلك يكون عدد الأقطار الرئيسية والأقطار المضادة $2n - 1$، أي أن طول المصفوفتين diags1 وdiags2 هو $2n - 1$.

/* حل مسألة الملكات n */
func nQueens(n int) [][][]string {
	// هيّئ رقعة شطرنج بحجم n*n، حيث تمثّل 'Q' ملكة و'#' خلية فارغة
	state := make([][]string, n)
	for i := 0; i < n; i++ {
		row := make([]string, n)
		for i := 0; i < n; i++ {
			row[i] = "#"
		}
		state[i] = row
	}
	// سجّل ما إذا كانت هناك ملكة في العمود
	cols := make([]bool, n)
	diags1 := make([]bool, 2*n-1)
	diags2 := make([]bool, 2*n-1)
	res := make([][][]string, 0)
	backtrack(0, n, &state, &res, &cols, &diags1, &diags2)
	return res
}

/* حل مسألة الملكات n */
function nQueens(n: number): string[][][] {
    // هيّئ رقعة شطرنج بحجم n*n، حيث تمثّل 'Q' ملكة و'#' خلية فارغة
    const state = Array.from({ length: n }, () => Array(n).fill('#'));
    const cols = Array(n).fill(false); // سجّل ما إذا كانت هناك ملكة في العمود
    const diags1 = Array(2 * n - 1).fill(false); // سجّل ما إذا كانت هناك ملكة على القطر الرئيسي
    const diags2 = Array(2 * n - 1).fill(false); // سجّل ما إذا كانت هناك ملكة على القطر المضاد
    const res: string[][][] = [];

    backtrack(0, n, state, res, cols, diags1, diags2);
    return res;
}

بوضع $n$ ملكة صفاً بصف، ومع مراعاة قيد العمود، يكون لدينا من الصف الأول إلى الصف الأخير $n$ و$n-1$ و$\dots$ و$2$ و$1$ خياراً، مستخدمين زمن $O(n!)$. وعند تسجيل حل، من الضروري نسخ المصفوفة state وإضافتها إلى res، وتستخدم عملية النسخ زمن $O(n^2)$. لذلك يكون التعقيد الزمني الكلي $O(n! \cdot n^2)$. وعملياً، يمكن للتشذيب استناداً إلى قيود الأقطار أيضاً أن يقلّص فضاء البحث تقليصاً كبيراً، لذا تكون كفاءة البحث غالباً أفضل من التعقيد الزمني المذكور أعلاه.

تستخدم المصفوفة state مساحة $O(n^2)$، وتستخدم المصفوفات cols وdiags1 وdiags2 مساحة $O(n)$ لكل منها. ويبلغ أقصى عمق للتعاود $n$، مستخدماً مساحة إطار مكدس $O(n)$. لذلك يكون التعقيد المكاني $O(n^2)$.