مسألة فأر في متاهة

مسألة فأر في متاهة

تقدّم هذه المسألة متاهة ممثّلة بواسطة مصفوفة ثنائية الأبعاد عناصرها هي N*N من الكتل، وتكون الكتلة الأولى في الجانب العلوي الأيسر من المصفوفة أي maze[0][0]‎ هي نقطة البداية، والكتلة الأخيرة في الجانب السفلي الأيمن من المصفوفة أي maze[N-1][N-1]‎ هي نقطة النهاية. يتحرك الفأر من نقطة البداية وعليه أن يصل إلى نقطة النهاية، ولكن ليس بمقدور الفأر أن يتحرك إلا باتجاهين هما الأمامي والسفلي.

يرمز الرقم 0 في مصفوفة المتاهة إلى الكتلة التي يكون فيها الطريق مسدودًا، ويرمز الرقم 1 إلى الكتلة التي يمكن استخدامها في المسار الواصل بين البداية والنهاية.

يعرض الشكل التالي مثالًا عن المتاهة، وتمثّل الكتل الرمادية طرقًا مسدودة (القيمة = 0).

يمكن تمثيل المتاهة السابقة بالمصفوفة الثنائية التالية:

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

يعرض الشكل التالية الحلّ الخاص بالمصفوفة السابقة (مخرجات البرنامج):

يمكن تمثيل الحلّ بالمصفوفة التالية:

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

يمثّل الرقم 1 في المخرجات المسار الذي سيسلكه الفأر من بداية المتاهة إلى نهايتها.

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

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

تتبع الخوارزمية البسيطة لحل مسألة فأر في متاهة الخطوات التالية:

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

1. ننشئ المسار التالي
   1. إن كانت جميع الكتل في هذا المسار تحمل الرقم 1
   2. نطبع هذا المسار

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

while there are untried paths
{
   generate the next path
   if this path has all blocks as 1
   {
      print this path;
   }
}

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

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

1. إن وصلنا إلى نقطة النهاية:

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

2. وإلا:

   1. نعلم الخلية الحالية في مصفوفة الحل بالقيمة 1.

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

   3. إن لم توصلنا الحركة السابقة إلى الحل، نتحرّك باتجاه الأسفل ونتحقّق ممّا إذا كانت هذه الحركة ستوصلنا إلى الحل.

   4. إن لم تفلح كلتا الحركتين السابقتين في إيصالنا إلى الحل نعلم هذه الخلية بالرقم 0 (التعقب الخلفي) ونعيد قيمة خاطئة.

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

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

• C++‎:

#include <stdio.h> 

// حجم المتاهة 
#define N 4 

bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]); 

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

/* دالة مساعدة للتحقق من أن القيم المعطاة هي مواقع ملائمة في مصفوفة المتاهة */
bool isSafe(int maze[N][N], int x, int y) 
{ 
	// إن كانت القيم المعطاة خارج المصفوفة، أعدنا قيمة خاطئة
	if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1) 
		return true; 

	return false; 
} 

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

	if (solveMazeUtil(maze, 0, 0, sol) == false) { 
		printf("Solution doesn't exist"); 
		return false; 
	} 

	printSolution(sol); 
	return true; 
} 

/* دالة مساعدة تعاودية لحل مسألة فأر في متاهة */
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]) 
{ 
	// y و x إن كانت
	// في نقطة النهاية نعيد قيمة صحيحة
	if (x == N - 1 && y == N - 1) { 
		sol[x][y] = 1; 
		return true; 
	} 

	// maze[x][y] التحقق من سلامة القيمة
	if (isSafe(maze, x, y) == true) { 
		// تعليم النقطتين كجزء من مسار الحل
		sol[x][y] = 1; 

		/* التحرّك باتجاه الأمام */
		if (solveMazeUtil(maze, x + 1, y, sol) == true) 
			return true; 

		/* x إن لم تؤد الحركة بالاتجاه الأمامي على المحور
		 y إلى الوصول للحلّ، تحرّكنا بالاتجاه السفلي على المحور */
		if (solveMazeUtil(maze, x, y + 1, sol) == true) 
			return true; 

		/* إن لم تنفع الحركتان السابقتان في التوصل إلى الحل ننفّذ أسلوب التعقب الخلفي
		y و x وذلك بإلغاء تعليم النقتطين 
		كجزء من مسار الحل */
		sol[x][y] = 0; 
		return false; 
	} 

	return false; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int maze[N][N] = { { 1, 0, 0, 0 }, 
					{ 1, 1, 0, 1 }, 
					{ 0, 1, 0, 0 }, 
					{ 1, 1, 1, 1 } }; 

	solveMaze(maze); 
	return 0; 
}

• بايثون:

# حجم المتاهة
N = 4

# دالة مساعدة لطباعة مصفوفة الحل 
def printSolution( sol ): 
	
	for i in sol: 
		for j in i: 
			print(str(j) + " ", end ="") 
		print("") 

# دالة مساعدة للتحقق من أن القيم المعطاة هي مواقع ملائمة في مصفوفة المتاهة 
def isSafe( maze, x, y ): 
	
	if x >= 0 and x < N and y >= 0 and y < N and maze[x][y] == 1: 
		return True
	
	return False

""" تحلّ هذه الدالة مسألة فأر في متاهة باستخدام التعقب الخلفي.
	solveMazeUtil() تعتمد هذه الدالة اعتمادًا كبيرًا على الدالة
	في حلّ هذه المسألة. وتعيد قيمة خاطئة في حال عدم وجود حل لهذه المسألة
	وتعيد قيمة صحيحة وتطبع الناتج في حال وجود الحل
	يجب الانتباه إلى وجود أكثر من حل لهذه المسألة وأنّ هذه الدالة
	تقدم أحد الحلول الممكنة فقط """
def solveMaze( maze ): 
	
	# إنشاء مصفوفة ثنائية الأبعاد ذات 4 صفوف و 4 أعمدة
	sol = [ [ 0 for j in range(4) ] for i in range(4) ] 
	
	if solveMazeUtil(maze, 0, 0, sol) == False: 
		print("Solution doesn't exist"); 
		return False
	
	printSolution(sol) 
	return True
	
# 
# دالة مساعدة تعاودية لحل مسألة فأر في متاهة 
def solveMazeUtil(maze, x, y, sol): 
	
	# y و x إن كانت
	# في نقطة النهاية نعيد قيمة صحيحة 
	if x == N - 1 and y == N - 1: 
		sol[x][y] = 1
		return True
		
	# maze[x][y] التحقق من سلامة القيمة
	if isSafe(maze, x, y) == True: 
		# تعليم النقطتين كجزء من مسار الحل 
		sol[x][y] = 1
		
		# التحرّك باتجاه الأمام
		if solveMazeUtil(maze, x + 1, y, sol) == True: 
			return True
			
		# x إن لم تؤد الحركة بالاتجاه الأمامي على المحور
		# y إلى الوصول للحلّ، تحرّكنا بالاتجاه السفلي على المحور 
		if solveMazeUtil(maze, x, y + 1, sol) == True: 
			return True
		
		# إن لم تنفع الحركتان السابقتان في التوصل إلى الحل ننفّذ أسلوب التعقب الخلفي
		# y و x وذلك بإلغاء تعليم النقتطين 
		# كجزء من مسار الحل 
		sol[x][y] = 0
		return False

# اختبار الدوال السابقة
if __name__ == "__main__": 
	# Initialising the maze 
	maze = [ [1, 0, 0, 0], 
			[1, 1, 0, 1], 
			[0, 1, 0, 0], 
			[1, 1, 1, 1] ] 
			
	solveMaze(maze)

• جافا:

public class RatMaze { 

	// حجم المتاهة 
	static int N; 

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

	/* دالة مساعدة للتحقق من أن القيم المعطاة هي مواقع ملائمة في مصفوفة المتاهة */
	boolean isSafe(int maze[][], int x, int y) 
	{ 
		// إن كانت القيم المعطاة خارج المصفوفة، أعدنا قيمة خاطئة 
		return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1); 
	} 

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

		if (solveMazeUtil(maze, 0, 0, sol) == false) { 
			System.out.print("Solution doesn't exist"); 
			return false; 
		} 

		printSolution(sol); 
		return true; 
	} 

	/* دالة مساعدة تعاودية لحل مسألة فأر في متاهة */
	boolean solveMazeUtil(int maze[][], int x, int y, 
						int sol[][]) 
	{ 
		// y و x إن كانت
		// في نقطة النهاية نعيد قيمة صحيحة
		if (x == N - 1 && y == N - 1) { 
			sol[x][y] = 1; 
			return true; 
		} 

		// maze[x][y] التحقق من سلامة القيمة
		if (isSafe(maze, x, y) == true) { 
			// تعليم النقطتين كجزء من مسار الحل 
			sol[x][y] = 1; 

			/* التحرّك باتجاه الأمام  */
			if (solveMazeUtil(maze, x + 1, y, sol)) 
				return true; 

			/* x إن لم تؤد الحركة بالاتجاه الأمامي على المحور
		 y إلى الوصول للحلّ، تحرّكنا بالاتجاه السفلي على المحور */
			if (solveMazeUtil(maze, x, y + 1, sol)) 
				return true; 

			/* إن لم تنفع الحركتان السابقتان في التوصل إلى الحل ننفّذ أسلوب التعقب الخلفي
		y و x وذلك بإلغاء تعليم النقتطين 
		كجزء من مسار الحل  */
			sol[x][y] = 0; 
			return false; 
		} 

		return false; 
	} 

	// اختبار التوابع السابقة
	
	public static void main(String args[]) 
	{ 
		RatMaze rat = new RatMaze(); 
		int maze[][] = { { 1, 0, 0, 0 }, 
						{ 1, 1, 0, 1 }, 
						{ 0, 1, 0, 0 }, 
						{ 1, 1, 1, 1 } }; 

		N = maze.length; 
		rat.solveMaze(maze); 
	} 
}

مصادر

• صفحة Rat in a Maze في توثيق الخوارزميات في موقع GeeksforGeeks.