مسألة ملكات الشطرنج

مسألة ملكات الشطرنج N Queen من مسائل لعبة الشطرنج وتتطلب وضع عدد معيّن من ملكات الشطرنج (ليكن N) على رقعة الشطرنج ذات الأبعاد N×N بشرط أن لا تستطيع أي ملكة مهاجمة الأخرى، بمعنى أن لا تكون هناك ملكتان في صفّ واحد أو عمود واحد وأن لا تتجاور ملكتان قطريًا.

يعرض الشكل التالي أحد حلول مسألة الملكات الأربعة (أي أنّ N = 4).

يقدّم البرنامج حلّ هذه المسألة على هيئة مصفوفة ثنائية تحتوي على الأرقام 0 و 1، ويمثّل الرقم 1 الخانات التي ستوضع فيها الملكات، فعلى سبيل المثال، يمكن التعبير عن الحل في الصورة السابقة بالمصفوفة التالية:

{ 0,  1,  0,  0}
{ 0,  0,  0,  1}
{ 1,  0,  0,  0}
{ 0,  0,  1,  0}

الخوارزمية البسيطة

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

تتبع الخوارزمية البسيطة لحل مسألة ملكات الشطرنج الخطوات التالية:

ما دامت هناك حالات لم تجرب بعد:

1. ننشئ الحالة التالية
   1. إن لم تستطع أي ملكة مهاجمة ملكة أخرى في هذه الحالة:
      1. نطبع هذه الحالة

توضح الشيفرة العامة التالية الخطوات آنفة الذكر:

while there are untried configurations
{


generate the next configuration
if queens don't attack in this configuration then
{
print this configuration;
}


}

التعقب الخلفي

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

تتبع الخوارزمية الخطوات التالية:

1. نبدأ بالعمود في أقصى اليسار

2. إن كانت جميع الملكات في مكانها الصحيح أعدنا قيمة صحيحة

3. نجرّب جميع الصفوف في العمود الحالي

   ننفّذ الخطوات التالية لكل صف مجرَّب:
   1. إن كان بالإمكان وضع الملكة في مكانها دون حدوث تضارب في هذا الصف نعلّم هذا الصف والعمود كجزء من الحل ونتحقق بطريقة تعاودية من أن وضع الملكة في هذا المكان سيؤدي للوصول إلى الحل.

   2. إن أدّى وضع الملكة في هذا الصف والعمود للوصول إلى الحل نعيد قيمة صحيحة.

   3. إن لم يؤدّ وضع الملكة هذا الصف والعمود للوصول إلى الحل نلغي تعليمهما (التعقب الخلفي) ونعود إلى الخطوة 1 لتجرب صفّ آخر.

4. إن جُرّبت جميع الصفوف ولم ينفع أيّ منها في إيجاد الحل، نعيد قيمة خاطئة وذلك لتنفيذ عملية التعقب الخلفي.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ خوارزمية حل مسألة ملكات الشطرنج باستخدام أسلوب التعقب الخلفي وفي عدد من لغات البرمجة:

• C++‎:

#define N 4 
#include <stdbool.h> 
#include <stdio.h> 

// دالة مساعدة لطباعة النتيجة
void printSolution(int board[N][N]) 
{ 
	for (int i = 0; i < N; i++) { 
		for (int j = 0; j < N; j++) 
			printf(" %d ", board[i][j]); 
		printf("\n"); 
	} 
} 

/* board[row][col] دالة مساعدة للتحق من إمكانية وضع الملكة في الموقع 
لاحظ أنّ هذه الدالة تستدعى عندما توضع الملكات في الأعمدة من العمود الأول إلى العمود الأخير
لذا سنحتاج إلى التحقق من هجوم الملكات من الجانب الأيسر فقط */

bool isSafe(int board[N][N], int row, int col) 
{ 
	int i, j; 

	/* تحقّق من هذا الصف من الجانب الأيسر */
	for (i = 0; i < col; i++) 
		if (board[row][i]) 
			return false; 

	/* التحقق من الجانب القطري العلوي في الجانب الأيسر */
	for (i = row, j = col; i >= 0 && j >= 0; i--, j--) 
		if (board[i][j]) 
			return false; 

	/* التحقق من الجانب القطري السفلي في الجانب الأيسر */
	for (i = row, j = col; j >= 0 && i < N; i++, j--) 
		if (board[i][j]) 
			return false; 

	return true; 
} 

/* دالة مساعدة تعاودية لحل مسألة ملكات الشطرنج */
bool solveNQUtil(int board[N][N], int col) 
{ 
	/* الحالة الأساس: إن كانت جميع الملكات موضوعة في مكانها، فسنعيد قيمة صحيحة */
	if (col >= N) 
		return true; 

	/* ننظر في هذا العمود ونحاول وضع هذه الملكة في جميع الصفوف واحدًا تلو الآخر */
	for (int i = 0; i < N; i++) { 
		/* board[i][col] التحقق من إمكانية وضع الملكة في الموقع */
		if (isSafe(board, i, col)) { 
			/*  board[i][col] وضع هذه الملكة في الموقع */
			board[i][col] = 1; 

			/* تنفذ العملية تعاوديًا وذلك لوضع بقية الملكات في مواقعها */
			if (solveNQUtil(board, col + 1)) 
				return true; 

			/*  board[i][col] إن لم يؤدِّ وضع الملكة في الموقع
			إلى الوصول إلى حل، تزال الملكة من هذا المكان */
			board[i][col] = 0; // التعقب الخلفي
		} 
	} 

	/* إن لم يكن بالإمكان وضع الملكة في أي صفّ من صفوف هذا العمود تعيد الدالة قيمة خاطئة */
	return false; 
} 

/* تحلّ هذه الدالة مسألة ملكات الشطرنج باستخدام التعقب الخلفي.
solveNQUtil() تعتمد هذه الدالة اعتمادًا كبيرًا على الدالة
في حلّ هذه المسألة. وتعيد قيمة خاطئة في حال عدم إمكانية وضع الملكات بالطريقة المطلوبة
وتعيد قيمة صحيحة وتطبع الناتج في حال وجود الحل
يجب الانتباه إلى وجود أكثر من حل لهذه المسألة وأنّ هذه الدالة
تقدم أحد الحلول الممكنة فقط */
bool solveNQ() 
{ 
	int board[N][N] = { { 0, 0, 0, 0 }, 
						{ 0, 0, 0, 0 }, 
						{ 0, 0, 0, 0 }, 
						{ 0, 0, 0, 0 } }; 

	if (solveNQUtil(board, 0) == false) { 
		printf("Solution does not exist"); 
		return false; 
	} 

	printSolution(board); 
	return true; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	solveNQ(); 
	return 0; 
}

• بايثون:

global N 
N = 4

def printSolution(board): 
	for i in range(N): 
		for j in range(N): 
			print (board[i][j], end = " ") 
		print() 

# board[row][col] دالة مساعدة للتحق من إمكانية وضع الملكة في الموقع 
# لاحظ أنّ هذه الدالة تستدعى عندما توضع الملكات في الأعمدة من العمود الأول إلى العمود الأخير
# لذا سنحتاج إلى التحقق من هجوم الملكات من الجانب الأيسر فقط
def isSafe(board, row, col): 

	# تحقّق من هذا الصف من الجانب الأيسر
	for i in range(col): 
		if board[row][i] == 1: 
			return False

	# التحقق من الجانب القطري العلوي في الجانب الأيسر 
	for i, j in zip(range(row, -1, -1), 
					range(col, -1, -1)): 
		if board[i][j] == 1: 
			return False

	# التحقق من الجانب القطري العلوي في الجانب الأيسر 
	for i, j in zip(range(row, N, 1), 
					range(col, -1, -1)): 
		if board[i][j] == 1: 
			return False

	return True

# دالة مساعدة تعاودية لحل مسألة ملكات الشطرنج

def solveNQUtil(board, col): 
	
	# الحالة الأساس: إن كانت جميع الملكات موضوعة في مكانها، فسنعيد قيمة صحيحة 
	if col >= N: 
		return True

	# ننظر في هذا العمود ونحاول وضع هذه الملكة
	# في جميع الصفوف واحدًا تلو الآخر 
	for i in range(N): 

		if isSafe(board, i, col): 
			
			# board[i][col] وضع هذه الملكة في الموقع 
			board[i][col] = 1

			# تنفذ العملية تعاوديًا وذلك لوضع بقية الملكات في مواقعها 
			if solveNQUtil(board, col + 1) == True: 
				return True

			# board[i][col] إن لم يؤدِّ وضع الملكة في الموقع
			# إلى الوصول إلى حل، تزال الملكة من هذا المكان 
			board[i][col] = 0 # التعقب الخلفي

	# إن لم يكن بالإمكان وضع الملكة في أي صفّ من صفوف هذا العمود تعيد الدالة قيمة خاطئة 
	return False

# تحلّ هذه الدالة مسألة ملكات الشطرنج باستخدام التعقب الخلفي.
# solveNQUtil() تعتمد هذه الدالة اعتمادًا كبيرًا على الدالة
# في حلّ هذه المسألة. وتعيد قيمة خاطئة في حال عدم إمكانية وضع الملكات بالطريقة المطلوبة
# وتعيد قيمة صحيحة وتطبع الناتج في حال وجود الحل
# يجب الانتباه إلى وجود أكثر من حل لهذه المسألة
# وأنّ هذه الدالة تقدم أحد الحلول الممكنة فقط

def solveNQ(): 
	board = [ [0, 0, 0, 0], 
			[0, 0, 0, 0], 
			[0, 0, 0, 0], 
			[0, 0, 0, 0] ] 

	if solveNQUtil(board, 0) == False: 
		print ("Solution does not exist") 
		return False

	printSolution(board) 
	return True

# اختبار الدوال السابقة
solveNQ()

• جافا:

public class NQueenProblem { 
	final int N = 4; 

	/* دالة مساعدة لطباعة النتيجة */
	void printSolution(int board[][]) 
	{ 
		for (int i = 0; i < N; i++) { 
			for (int j = 0; j < N; j++) 
				System.out.print(" " + board[i][j] 
								+ " "); 
			System.out.println(); 
		} 
	} 

	/* board[row][col] دالة مساعدة للتحق من إمكانية وضع الملكة في الموقع 
	لاحظ أنّ هذه الدالة تستدعى عندما توضع الملكات في الأعمدة من العمود الأول إلى العمود الأخير
	لذا سنحتاج إلى التحقق من هجوم الملكات من الجانب الأيسر فقط */
	boolean isSafe(int board[][], int row, int col) 
	{ 
		int i, j; 

		/* تحقّق من هذا الصف من الجانب الأيسر */
		for (i = 0; i < col; i++) 
			if (board[row][i] == 1) 
				return false; 

		/* التحقق من الجانب القطري العلوي في الجانب الأيسر */
		for (i = row, j = col; i >= 0 && j >= 0; i--, j--) 
			if (board[i][j] == 1) 
				return false; 

		/* التحقق من الجانب القطري السفلي في الجانب الأيسر */
		for (i = row, j = col; j >= 0 && i < N; i++, j--) 
			if (board[i][j] == 1) 
				return false; 

		return true; 
	} 

	/* دالة مساعدة تعاودية لحل مسألة ملكات الشطرنج */
	boolean solveNQUtil(int board[][], int col) 
	{ 
		/* الحالة الأساس: إن كانت جميع الملكات موضوعة في مكانها، فسنعيد قيمة صحيحة */
		if (col >= N) 
			return true; 

		/* ننظر في هذا العمود ونحاول وضع هذه الملكة في جميع الصفوف واحدًا تلو الآخر */
		for (int i = 0; i < N; i++) { 
			/* board[i][col] التحقق من إمكانية وضع الملكة في الموقع */
			if (isSafe(board, i, col)) { 
				/* board[i][col] وضع هذه الملكة في الموقع */
				board[i][col] = 1; 

				/* تنفذ العملية تعاوديًا وذلك لوضع بقية الملكات في مواقعها */
				if (solveNQUtil(board, col + 1) == true) 
					return true; 

				/* board[i][col] إن لم يؤدِّ وضع الملكة في الموقع 
				إلى الوصول إلى حل، تزال الملكة من هذا المكان */
				board[i][col] = 0; // التعقب الخلفي 
			} 
		} 

		/* إن لم يكن بالإمكان وضع الملكة في أي صفّ من صفوف هذا العمود تعيد الدالة قيمة خاطئة */
		return false; 
	} 

	/* تحلّ هذه الدالة مسألة ملكات الشطرنج باستخدام التعقب الخلفي.
	solveNQUtil() تعتمد هذه الدالة اعتمادًا كبيرًا على الدالة
	في حلّ هذه المسألة. وتعيد قيمة خاطئة في حال عدم إمكانية وضع الملكات بالطريقة المطلوبة
	وتعيد قيمة صحيحة وتطبع الناتج في حال وجود الحل
	يجب الانتباه إلى وجود أكثر من حل لهذه المسألة وأنّ هذه الدالة
	تقدم أحد الحلول الممكنة فقط*/
	boolean solveNQ() 
	{ 
		int board[][] = { { 0, 0, 0, 0 }, 
						{ 0, 0, 0, 0 }, 
						{ 0, 0, 0, 0 }, 
						{ 0, 0, 0, 0 } }; 

		if (solveNQUtil(board, 0) == false) { 
			System.out.print("Solution does not exist"); 
			return false; 
		} 

		printSolution(board); 
		return true; 
	} 

	// اختبار التوابع السابقة
	public static void main(String args[]) 
	{ 
		NQueenProblem Queen = new NQueenProblem(); 
		Queen.solveNQ(); 
	} 
}

تعطي الشيفرة السابقة المخرجات التالية:

0  0  1  0 
1  0  0  0 
0  0  0  1 
0  1  0  0

يشير الرقم 1 إلى مواقع الملكات في رقعة الشطرنج.

مصادر

• صفحة N Queen Problem في توثيق الخوارزميات في موقع GeeksforGeeks.