Algorithms/Knights tour

يوضع الحصان في الخانة الأولى من رقعة شطرنج فارغة، ويجب أن يتحرك الفارس وفق قواعد الشطرنج ليزور كل مربع في رقعة الشطرنج مرة واحدة فقط، تسمى هذه المسألة بجولة الحصان Knight's Tour.

يمثل الجدول التالي رقعة شطرنج ذات 8 × 8 خانة، وتمثّل الأرقام في كل خانة رقم حركة الحصان.

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

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

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

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

1. ننشئ الجولة التالية
   1. إن كانت هذه الجولة تغطّي جميع المربعات:
      1. نطبع هذا المسار

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

while there are untried tours
{ 
   generate the next tour 
   if this tour covers all squares 
   { 
      print this path;
   }
}

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

يعمل نموذج التعقب الخلفي بطريقة تصاعدية في حل المسألة، إذ يبدأ عادة من مصفوفة حلول فارغة ثم يضيف العناصر إليها واحداً تلو الآخر (يختلف المفهوم الذي يمثّله العنصر بين مسألة وأخرى، ففي سياق مسألة جولة الحصان، يمثّل العنصر حركة الفارس)، وعند إضافة العنصر تتحقّق الخوارزمية من أنّ إضافة ذلك العنصر لا تشكّل خرقًا للقيود المفروضة من قبل المسألة، فإن كان كذلك يُحذف العنصر من المصفوفة ويجرّب حل آخر، وإن فشلت كل الحلول في تحقيق القيد المفروض من قبل المسألة تعود الخوارزمية إلى المرحلة السابقة وتحذف العنصر الذي أضيف في تلك المرحلة، وإن وصلت الخوارزمية إلى المرحلة الأولى فنقول حينئذٍ أنّ المسألة المعنية لا تمتلك أيّ حلول. أما إذا لم تؤدِّ إضافة العنصر إلى الخروج عن القيود المفروضة من قبل المسألة فستُضاف العناصر واحدًا تلو الآخر بطريقة تعاودية.

تتبع خوارزمية حل مسألة جولة الحصان بالاعتماد على نموذج التعقب الخلفي الخطوات التالية:

إن كانت كل المربعات مزورة:

نطبع حلّ المسألة.

وإلا:

1. نضيف إحدى الحركات التالية إلى مصفوفة الحل ونتحقق بطريقة تعاودية ممّا إذا كانت هذه الحركة ستوصلنا إلى الحل (يمكن للحصان أن يتحرّك 8 حركات كحدٍّ أقصى، وسنختار إحدى هذه الحركات الثمانية في هذه الخطوة).

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

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

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

تعرض الأمثلة التالية طريقة حل مسألة جولة الحصان باستخدام نموذج التعقب الخلفي في عدد من لغات البرمجة. تطبع الشيفرة التالي الحلول في مصفوفة matrix ثنائي الأبعاد، والمخرجات هي عبارة عن مصفوفة ثنائية الأبعاد ذات 8 صفوف و8 أعمدة (8×8)، تتضمن مجموعة الأرقام التي تبدأ من 0 وتنتهي بالرقم 63، وتمثّل هذه الأرقام الخطوات التي يؤدّيها الحصان على رقعة الشطرنج.

• C++‎:

#include<stdio.h> 
#define N 8 

int solveKTUtil(int x, int y, int movei, int sol[N][N], 
				int xMove[], int yMove[]); 

/* دالة مساعدة للتحقق من أنّ القيم المعطاة ملائمة لمصفوفة رقعة الشطرنج */
bool isSafe(int x, int y, int sol[N][N]) 
{ 
	return ( x >= 0 && x < N && y >= 0 && 
			y < N && sol[x][y] == -1); 
} 

/* دالة مساعدة لطباعة مصفوفة الحل */
void printSolution(int sol[N][N]) 
{ 
	for (int x = 0; x < N; x++) 
	{ 
		for (int y = 0; y < N; y++) 
			printf(" %2d ", sol[x][y]); 
		printf("\n"); 
	} 
} 

/* تحلّ هذه الدالة مسألة جولة الحصان باستخدام التعقب الخلفي.
solveKTUtil() تعتمد هذه الدالة اعتمادًا كبيرًا على الدالة
في حلّ هذه المسألة. وتعيد قيمة خاطئة في حال عدم وجود حل لهذه المسألة
وتعيد قيمة صحيحة وتطبع الناتج في حال وجود الحل
يجب الانتباه إلى وجود أكثر من حل لهذه المسألة وأنّ هذه الدالة
تقدم أحد الحلول الممكنة فقط */
bool solveKT() 
{ 
	int sol[N][N]; 

	/* تهيئة مصفوفة الحل */
	for (int x = 0; x < N; x++) 
		for (int y = 0; y < N; y++) 
			sol[x][y] = -1; 

	/* تحدد هاتان المصفوفتان الحركة القادمة للحصان
	xMove[] لحركة الحصان القادمة على المحور السيني
	yMove[] لحركة الحصان القادمة على المحور الصادي */
	
	int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; 
	int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; 

	// لما كان الحصان في بداية الخوارزمية في الخانة الأولى
	sol[0][0] = 0; 

	/* solveKTUtil() البدء من الخانة 0,0 واستكشاف جميع الحركات باستخدام الدالة */
	if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == false) 
	{ 
		printf("Solution does not exist"); 
		return false; 
	} 
	else
		printSolution(sol); 

	return true; 
} 

/* دالة مساعدة تعاودية تستخدم لحلّ مسألة جولة الحصان */
int solveKTUtil(int x, int y, int movei, int sol[N][N], 
				int xMove[N], int yMove[N]) 
{ 
int k, next_x, next_y; 
if (movei == N*N) 
	return true; 

/* x, y تجربة جميع الحركات القادمة من الموقع الحالي ذي الإحداثيات */

for (k = 0; k < 8; k++) 
{ 
	next_x = x + xMove[k]; 
	next_y = y + yMove[k]; 
	if (isSafe(next_x, next_y, sol)) 
	{ 
		sol[next_x][next_y] = movei; 
		if (solveKTUtil(next_x, next_y, movei+1, sol, 
						xMove, yMove) == true) 
			return true; 
		else
			sol[next_x][next_y] = -1; // التعقب الخلفي
	} 
} 

return false; 
} 

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

• بايثون:

n = 8

def isSafe(x,y,board): 
	''' 
		دالة مساعدة للتحقق من أنّ القيم المعطاة ملائمة لمصفوفة رقعة الشطرنج 
	'''
	if(x >= 0 and y >= 0 and x < n and y < n and board[x][y] == -1): 
		return True
	return False

def printSolution(board): 
	''' 
		دالة مساعدة لطباعة مصفوفة الحل 
	'''
	for i in range(n): 
		for j in range(n): 
			print(board[i][j],end =' ') 
		print() 


def solveKT(): 
	''' 
	تحلّ هذه الدالة مسألة جولة الحصان باستخدام التعقب الخلفي.
	solveKTUtil() تعتمد هذه الدالة اعتمادًا كبيرًا على الدالة
	في حلّ هذه المسألة. وتعيد قيمة خاطئة في حال عدم وجود حل لهذه المسألة
	وتعيد قيمة صحيحة وتطبع الناتج في حال وجود الحل
	يجب الانتباه إلى وجود أكثر من حل لهذه المسألة وأنّ هذه الدالة
	تقدم أحد الحلول الممكنة فقط 
	'''
	
	# تهيئة مصفوفة الحل 
	board = [[-1 for i in range(n)]for i in range(n)] 
	
	# تحدد هاتان المصفوفتان الحركة القادمة للحصان 
	# xMove[] لحركة الحصان القادمة على المحور السيني 
	# yMove[] لحركة الحصان القادمة على المحور الصادي 
	move_x = [2, 1, -1, -2, -2, -1, 1, 2] 
	move_y = [1, 2, 2, 1, -1, -2, -2, -1] 
	
	# لما كان الحصان في بداية الخوارزمية في الخانة الأولى 
	board[0][0] = 0
	
	# عداد لموقع الحصان في الرقعة
	pos = 1
	
	# التحقق ممّا إذا كان الحل موجودًا أم لا
	if(not solveKTUtil(board, 0, 0, move_x, move_y, pos)): 
		print("Solution does not exist") 
	else: 
		printSolution(board) 

def solveKTUtil(board,curr_x,curr_y,move_x,move_y,pos): 
	''' 
		دالة مساعدة تعاودية تستخدم لحلّ مسألة جولة الحصان
	'''
	
	if(pos == n**2): 
		return True
	
	# x, y تجربة جميع الحركات القادمة من الموقع الحالي ذي الإحداثيات 
	for i in range(8): 
		new_x = curr_x + move_x[i] 
		new_y = curr_y + move_y[i] 
		if(isSafe(new_x,new_y,board)): 
			board[new_x][new_y] = pos 
			if(solveKTUtil(board,new_x,new_y,move_x,move_y,pos+1)): 
				return True
			
			# التعقب الخلفي 
			board[new_x][new_y] = -1
	return False
		
# اختبار الدوال السابقة 
if __name__ == "__main__": 
	solveKT()

• جافا:

class KnightTour { 
	static int N = 8; 

	/* دالة مساعدة للتحقق من أنّ القيم المعطاة ملائمة لمصفوفة رقعة الشطرنج */
	static boolean isSafe(int x, int y, int sol[][]) { 
		return (x >= 0 && x < N && y >= 0 && 
				y < N && sol[x][y] == -1); 
	} 

	/* دالة مساعدة لطباعة مصفوفة الحل */
	static void printSolution(int sol[][]) { 
		for (int x = 0; x < N; x++) { 
			for (int y = 0; y < N; y++) 
				System.out.print(sol[x][y] + " "); 
			System.out.println(); 
		} 
	} 

	/* تحلّ هذه الدالة مسألة جولة الحصان باستخدام التعقب الخلفي.
	solveKTUtil() تعتمد هذه الدالة اعتمادًا كبيرًا على الدالة
	في حلّ هذه المسألة. وتعيد قيمة خاطئة في حال عدم وجود حل لهذه المسألة
	وتعيد قيمة صحيحة وتطبع الناتج في حال وجود الحل
	يجب الانتباه إلى وجود أكثر من حل لهذه المسألة وأنّ هذه الدالة
	تقدم أحد الحلول الممكنة فقط
	*/
	static boolean solveKT() { 
		int sol[][] = new int[8][8]; 

		/* تهيئة مصفوفة الحل */
		for (int x = 0; x < N; x++) 
			for (int y = 0; y < N; y++) 
				sol[x][y] = -1; 

	/* تحدد هاتان المصفوفتان الحركة القادمة للحصان
	xMove[] لحركة الحصان القادمة على المحور السيني
	yMove[] لحركة الحصان القادمة على المحور الصادي */
		int xMove[] = {2, 1, -1, -2, -2, -1, 1, 2}; 
		int yMove[] = {1, 2, 2, 1, -1, -2, -2, -1}; 

		// لما كان الحصان في بداية الخوارزمية في الخانة الأولى
		sol[0][0] = 0; 

		/* solveKTUtil() البدء من الخانة 0,0 واستكشاف جميع الحركات باستخدام الدالة */
		if (!solveKTUtil(0, 0, 1, sol, xMove, yMove)) { 
			System.out.println("Solution does not exist"); 
			return false; 
		} else
			printSolution(sol); 

		return true; 
	} 

	/* دالة مساعدة تعاودية تستخدم لحلّ مسألة جولة الحصان */
	static boolean solveKTUtil(int x, int y, int movei, 
							int sol[][], int xMove[], 
							int yMove[]) { 
		int k, next_x, next_y; 
		if (movei == N * N) 
			return true; 

		/* x, y تجربة جميع الحركات القادمة من الموقع الحالي ذي الإحداثيات */
		for (k = 0; k < 8; k++) { 
			next_x = x + xMove[k]; 
			next_y = y + yMove[k]; 
			if (isSafe(next_x, next_y, sol)) { 
				sol[next_x][next_y] = movei; 
				if (solveKTUtil(next_x, next_y, movei + 1, 
								sol, xMove, yMove)) 
					return true; 
				else
					sol[next_x][next_y] = -1;// التعقب الخلفي 
			} 
		} 

		return false; 
	} 

	/* اختبار الدوال السابقة */
	public static void main(String args[]) { 
		solveKT(); 
	} 
}

مصادر

• صفحة The Knight’s tour problem في توثيق الخوارزميات في موقع GeeksforGeeks.