السودوكو

تستخدم لعبة السودوكو Sudoku مصفوفة ثنائية الأبعاد حجمها 9×9 (سنعبّر عنها grid[9][9]‎) وتحتوي على بعض الأرقام، والهدف هو تعبئة هذه المصفوفة بالأرقام (من 1 إلى 9) بشرط أن لا يتكرّر أي رقم من الأرقام (1 إلى 9) في كل صف وعمود ومصفوفة فرعية ذات حجم 3×3 إطلاقًا.

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

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

طريقة التعقب الخلفي

يمكن حلّ مسألة سودوكو -كما هو الحال مع جميع مسائل التعقب الخلفي- بإسناد الأرقام إلى الخلايا الفارغة واحدة تلو الأخرى، وقبل إسناد العدد نتحقّق ممّا إذا كانت إضافة العدد في هذه الخلية مسموحة أو لا. يجري التحقق ببساطة من وجود العدد نفسه في الصف الحالي، وفي العمود الحالي وفي المصفوفة الفرعية ذات الحجم 3×3. بعد التحقق من إمكانية الإضافة، نسند الرقم ونتحقق بطريقة تعاودية من أنّ عملية الإسناد هذه ستوصلنا إلى الحلّ، فإن لم تنفع عملية الإسناد هذه نجرّب الرقم التالي للخلية الفارغة الحالية، وإن لم نتمكن من الوصول إلى الحل باستخدام الأرقام 1 إلى 9 نعيد قيمة خاطئة.

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

1. ابحث عن صف، عمود لخلية فارغة
2. إن لم يكن هناك أيّ خلية فارغة نعيد قيمة صحيحة
3. ننفّذ الخطوات التالية للأرقام من 1 إلى 9
   1. إن لم يكن هناك رقم مكرّر في الصف أو العمود الحالي نعين ذلك الرقم للصف أو العمود الحالي ونحاول تعبئة بقية الخلايا بطريقة تعاودية
   2. إن كانت العملية التعاودية ناجحة، أعدنا قيمة صحيحة
   3. وإلا، نحذف الرقم ونجرّب رقمًا آخر
4. إن جربنا جميع الأرقام ولم نصل إلى نتيجة، نعيد قيمة خاطئة

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

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

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// للتعبير عن الخلايا الفارغة في مصفوفة سودوكو
#define UNASSIGNED 0 

// للتعبير عن أبعاد مصفوفة سودوكو
// N×N ستكون الأبعاد
#define N 9 

// تعثر هذه الدالة على الخلايا الفارغة في المصفوفة
bool FindUnassignedLocation(int grid[N][N], 
							int &row, int &col); 

// تتحقق هذه الدالة من إمكانية تعيين رقم إلى الصف والعمود المعطيين
bool isSafe(int grid[N][N], int row, 
				int col, int num); 

/* تأخذ هذه الدالة مصفوفة غير مملوءة بالكامل وتحاول
تعيين قيم لجميع المواقع الفارغة فيها بطريقة تتوافق
مع الشروط المطلوبة لحلة مسألة سودوكو
(لا تكرار للأرقام في الصفوف والأعمدة والصناديق)
*/

bool SolveSudoku(int grid[N][N]) 
{ 
	int row, col; 

	// إن لم يكن هناك أي خلية فارغة ينتهي عمل الدالة
	if (!FindUnassignedLocation(grid, row, col)) 
	return true; 

	// تنفيذ الحلقة التكرارية للأرقام من 1 إلى 9
	for (int num = 1; num <= 9; num++) 
	{ 
		// إن كان بالإمكان إضافة الرقم في الصف والعمود
		if (isSafe(grid, row, col, num)) 
		{ 
			// إسناد الرقم إلى الخلية في الصف والعمود المحددين مؤقتًا
			grid[row][col] = num; 

			// إعادة قيمة صحيحة إن كانت العملية ناجحة
			if (SolveSudoku(grid)) 
				return true; 

			// إن لم نحصل على الحل نلغي عملية الإسناد ونجرب رقمًا آخر
			// failure, unmake & try again 
			grid[row][col] = UNASSIGNED; 
		} 
	} 
	return false; // التعقب الخلفي 
} 


/* تبحث هذه الدالة في المصفوفة عن الخلايا التي لم تُسند إليها الأرقام بعد.
إن عثرت الدالة على خلية، ستستخدم الصف والعمود المعطيين كإشارة
لتعيين الموقع الذي لم تُسند إليه الأرقام، وتعيد قيمة صحيحة.
وإن لم تعثر الدالة على خلايا، فإنّها تعيد قيمة خاطئة */ 
bool FindUnassignedLocation(int grid[N][N], 
							int &row, int &col) 
{ 
	for (row = 0; row < N; row++) 
		for (col = 0; col < N; col++) 
			if (grid[row][col] == UNASSIGNED) 
				return true; 
	return false; 
} 

/* تعيد الدالة قيمة منطقية تحدّد ما إذا كانت القيمة المسندة
في الصف المعطى مطابقة للرقم المعطى */
bool UsedInRow(int grid[N][N], int row, int num) 
{ 
	for (int col = 0; col < N; col++) 
		if (grid[row][col] == num) 
			return true; 
	return false; 
} 

/* تعيد الدالة قيمة منطقية تحدّد ما إذا كانت القيمة المسندة
في العمود المعطى مطابقة للرقم المعطى */
bool UsedInCol(int grid[N][N], int col, int num) 
{ 
	for (int row = 0; row < N; row++) 
		if (grid[row][col] == num) 
			return true; 
	return false; 
} 

/* تعيد الدالة قيمة منطقية تحدّد ما إذا كانت القيمة المسندة
في الصندوق ذي الأبعاد 3×3 المعطى مطابقة للرقم المعطى */
bool UsedInBox(int grid[N][N], int boxStartRow, 
			int boxStartCol, int num) 
{ 
	for (int row = 0; row < 3; row++) 
		for (int col = 0; col < 3; col++) 
			if (grid[row + boxStartRow] 
					[col + boxStartCol] == num) 
				return true; 
	return false; 
} 

/* تعيد الدالة قيمة منطقية تحدّد ما إذا بالإمكان إسناد
الرقم المعطى إلى الصف والعمود المعطيين */
bool isSafe(int grid[N][N], int row, 
				int col, int num) 
{ 
	/* يجري التحقق من أنّ الرقم المعطى ليس موضوعًا أصلًا في
	الصف الحالي والعمود الحالي والصندوق ذي الأبعاد 3×3 الحالي */
	return !UsedInRow(grid, row, num) && 
		!UsedInCol(grid, col, num) && 
		!UsedInBox(grid, row - row % 3 , 
					col - col % 3, num) && 
			grid[row][col] == UNASSIGNED; 
} 

/* دالة مساعدة لطباعة مصفوفة النتيجة */
void printGrid(int grid[N][N]) 
{ 
	for (int row = 0; row < N; row++) 
	{ 
	for (int col = 0; col < N; col++) 
			cout << grid[row][col] << " "; 
		cout << endl; 
	} 
} 

// اختبار الدالة السابقة
int main() 
{ 
	// الرقم 0 يعني أن الخلية فارغة 
	int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0}, 
					{5, 2, 0, 0, 0, 0, 0, 0, 0}, 
					{0, 8, 7, 0, 0, 0, 0, 3, 1}, 
					{0, 0, 3, 0, 1, 0, 0, 8, 0}, 
					{9, 0, 0, 8, 6, 3, 0, 0, 5}, 
					{0, 5, 0, 0, 9, 0, 6, 0, 0}, 
					{1, 3, 0, 0, 0, 0, 2, 5, 0}, 
					{0, 0, 0, 0, 0, 0, 0, 7, 4}, 
					{0, 0, 5, 2, 0, 6, 3, 0, 0}}; 
	if (SolveSudoku(grid) == true) 
		printGrid(grid); 
	else
		cout << "No solution exists"; 

	return 0; 
}

• بايثون:

# دالة مساعدة لطباعة مصفوفة النتيجة
def print_grid(arr): 
	for i in range(9): 
		for j in range(9): 
			print arr[i][j], 
		print ('n') 

		
# تبحث هذه الدالة عن الخلية التي لم تستخدم بعد في المصفوفة
# تبحث هذه الدالة في المصفوفة عن الخلايا التي لم تُسند إليها الأرقام بعد.
# إن عثرت الدالة على خلية، ستستخدم الصف والعمود المعطيين كإشارة وتعيد الدالة قيمة صحيحة
# وإن لم تبق خلية فارغة تعيد الدالة قيمة خاطئة
# 'l' هو متغير يمثّل قائمة جرى تمريرها من الدالة solve_sudoku
# وذلك لمتابعة الزيادة في الصفوفة والأعمدة
def find_empty_location(arr,l): 
	for row in range(9): 
		for col in range(9): 
			if(arr[row][col]==0): 
				l[0]=row 
				l[1]=col 
				return True
	return False

# تعيد الدالة قيمة منطقية تحدّد ما إذا كانت
# القيمة المسندة في الصف المعطى مطابقة للرقم المعطى
def used_in_row(arr,row,num): 
	for i in range(9): 
		if(arr[row][i] == num): 
			return True
	return False

# تعيد الدالة قيمة منطقية تحدّد ما إذا كانت
# القيمة المسندة في العمود المعطى مطابقة للرقم المعطى
def used_in_col(arr,col,num): 
	for i in range(9): 
		if(arr[i][col] == num): 
			return True
	return False

# تعيد الدالة قيمة منطقية تحدّد ما إذا كانت
# القيمة المسندة في الصندوق ذي الأبعاد 3×3 المعطى مطابقة للرقم المعطى
def used_in_box(arr,row,col,num): 
	for i in range(3): 
		for j in range(3): 
			if(arr[i+row][j+col] == num): 
				return True
	return False


# تعيد الدالة قيمة منطقية تحدّد ما إذا بالإمكان إسناد
# الرقم المعطى إلى الصف والعمود المعطيين
def check_location_is_safe(arr,row,col,num): 
	
	#  يجري التحقق من أنّ الرقم المعطى ليس موضوعًا أصلًا في 
	# الصف الحالي والعمود الحالي والصندوق ذي الأبعاد 3×3 الحالي 
	return not used_in_row(arr,row,num) and not used_in_col(arr,col,num) and not used_in_box(arr,row - row%3,col - col%3,num) 

# تأخذ هذه الدالة مصفوفة غير مملوءة بالكامل وتحاول
# تعيين قيم لجميع المواقع الفارغة فيها بطريقة تتوافق
# مع الشروط المطلوبة لحلة مسألة سودوكو
# (لا تكرار للأرقام في الصفوف والأعمدة والصناديق)
def solve_sudoku(arr): 
	
	# تستخدم هذه القائمة لمتابعة عمليات الزيادة
	# find_empty_location التي تُجرى على الصفوف والأعمدة في دالة
	l=[0,0] 
	
	# إن لم يكن هناك أي خلية فارغة ينتهي عمل الدالة
	if(not find_empty_location(arr,l)): 
		return True
	
	# إسناد القيم في القائمة إلى الصف والعمود
	# الذين حصلنا عليهما من الدالة السابقة
	row=l[0] 
	col=l[1] 
	
	# 
	# تنفيذ الحلقة التكرارية للأرقام من 1 إلى 9
	for num in range(1,10): 
		
		# إن كان بالإمكان إضافة الرقم في الصف والعمود 
		if(check_location_is_safe(arr,row,col,num)): 
			
			# إسناد القيمة مؤقتًا 
			arr[row][col]=num 

			# إعادة قيمة صحيحة إن كانت العملية ناجحة 
			if(solve_sudoku(arr)): 
				return True

			# إن لم نحصل على الحل نلغي عملية الإسناد ونجرب رقمًا آخر 
			arr[row][col] = 0
			
	# التعقب الخلفي 
	return False

# اختبار الدالة السابقة
if __name__=="__main__": 
	
	# إنشاء مصفوفة ثنائية الأبعاد
	grid=[[0 for x in range(9)]for y in range(9)] 
	
	# assigning values to the grid 
	grid=[[3,0,6,5,0,8,4,0,0], 
		[5,2,0,0,0,0,0,0,0], 
		[0,8,7,0,0,0,0,3,1], 
		[0,0,3,0,1,0,0,8,0], 
		[9,0,0,8,6,3,0,0,5], 
		[0,5,0,0,9,0,6,0,0], 
		[1,3,0,0,0,0,2,5,0], 
		[0,0,0,0,0,0,0,7,4], 
		[0,0,5,2,0,6,3,0,0]] 
	
	# طباعة المصفوفة في حالة نجاح عمل الدالة
	if(solve_sudoku(grid)): 
		print_grid(grid) 
	else: 
		print "No solution exists"

• جافا:

class GFG 
{ 
public static boolean isSafe(int[][] board, 
							int row, int col, 
							int num) 
{ 
	// عدم تكرار الأرقام في الصف
	for (int d = 0; d < board.length; d++) 
	{ 
		// إن كان الرقم الذي نحاول وضعه موجود
		// أصلًا في ذلك الصف نعيد قيمة خاطئة
		if (board[row][d] == num) 
		{ 
			return false; 
		} 
	} 
	
	// عدم تكرار الأرقام في العمود
	for (int r = 0; r < board.length; r++) 
	{ 
		// إن كان الرقم الذي نحاول وضعه موجود
		// أصلًا في ذلك العمود نعيد قيمة خاطئة
		
		if (board[r][col] == num) 
		{ 
			return false; 
		} 
	} 

	// عدم تكرار الأرقام في الصندوق
	int sqrt = (int) Math.sqrt(board.length); 
	int boxRowStart = row - row % sqrt; 
	int boxColStart = col - col % sqrt; 

	for (int r = boxRowStart; 
			r < boxRowStart + sqrt; r++) 
	{ 
		for (int d = boxColStart; 
				d < boxColStart + sqrt; d++) 
		{ 
			if (board[r][d] == num) 
			{ 
				return false; 
			} 
		} 
	} 

		// يمكن إضافة الرقم إن لم يحصل أي تضارب
	return true; 
} 

public static boolean solveSudoku(int[][] board, int n) 
{ 
	int row = -1; 
	int col = -1; 
	boolean isEmpty = true; 
	for (int i = 0; i < n; i++) 
	{ 
		for (int j = 0; j < n; j++) 
		{ 
			if (board[i][j] == 0) 
			{ 
				row = i; 
				col = j; 
				
				// ما زالت هناك بعض القيم
				// الناقصة في مسألة سودوكو
				isEmpty = false; 
				break; 
			} 
		} 
		if (!isEmpty) 
		{ 
			break; 
		} 
	} 

	// لم تبق أي مساحة فارغة
	if (isEmpty) 
	{ 
		return true; 
	} 

	// وإلا نجري التعقب الخلفي لكل صفّ
	for (int num = 1; num <= n; num++) 
	{ 
		if (isSafe(board, row, col, num)) 
		{ 
			board[row][col] = num; 
			if (solveSudoku(board, n)) 
			{ 
				// print(board, n); 
				return true; 
			} 
			else
			{ 
				board[row][col] = 0; // استبدال القمية
			} 
		} 
	} 
	return false; 
} 

public static void print(int[][] board, int N) 
{ 
	// حصلنا على الإجابة وسنطبعها فقط
	for (int r = 0; r < N; r++) 
	{ 
		for (int d = 0; d < N; d++) 
		{ 
			System.out.print(board[r][d]); 
			System.out.print(" "); 
		} 
		System.out.print("\n"); 
		
		if ((r + 1) % (int) Math.sqrt(N) == 0) 
		{ 
			System.out.print(""); 
		} 
	} 
} 

// اختبار التوابع السابقة
public static void main(String args[]) 
{ 

	int[][] board = new int[][] 
	{ 
			{3, 0, 6, 5, 0, 8, 4, 0, 0}, 
			{5, 2, 0, 0, 0, 0, 0, 0, 0}, 
			{0, 8, 7, 0, 0, 0, 0, 3, 1}, 
			{0, 0, 3, 0, 1, 0, 0, 8, 0}, 
			{9, 0, 0, 8, 6, 3, 0, 0, 5}, 
			{0, 5, 0, 0, 9, 0, 6, 0, 0}, 
			{1, 3, 0, 0, 0, 0, 2, 5, 0}, 
			{0, 0, 0, 0, 0, 0, 0, 7, 4}, 
			{0, 0, 5, 2, 0, 6, 3, 0, 0} 
	}; 
	int N = board.length; 

	if (solveSudoku(board, N)) 
	{ 
		print(board, N); // طباعة الحل
	} 
	else
	{ 
		System.out.println("No solution"); 
	} 
} 
}

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

  3 1 6 5 7 8 4 9 2
  5 2 9 1 3 4 7 6 8
  4 8 7 6 2 9 5 3 1
  2 6 3 4 1 5 9 8 7
  9 7 4 8 6 3 1 2 5
  8 5 1 7 9 2 6 4 3
  1 3 8 9 4 7 2 5 6
  6 9 2 3 5 1 8 7 4
  7 4 5 2 8 6 3 1 9

مصادر

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