الگوریتم حل سودوکو یکی از مسائل پرطرفدار در دنیای پازل‌ها و مسائل منطقی است که نیاز به یافتن راه‌حل‌هایی برای تکمیل ماتریس‌های ناقص سودوکو دارد. در این مقاله از مجموعه مقالات آموزشی پی استور ، به بررسی انواع الگوریتم حل سودوکو پرداخته‌ایم. ابتدا با معرفی الگوریتم بازگشتی «Backtracking»، رویکردی پایه‌ای برای حل سودوکو ارائه می‌شود که در آن برای هر خانه غیرمنتسب، اعداد ۱ تا ۹ به صورت بازگشتی امتحان می‌شوند. این روش به‌عنوان الگوریتم حل سودوکو ساده و کارآمد شناخته می‌شود، اما پیچیدگی زمانی بالایی دارد.
در ادامه، به بررسی بهینه‌سازی الگوریتم حل سودوکو با استفاده از ماسک بیت «Bit Masking» می‌پردازیم. در این روش، با ایجاد سه آرایه برای سطرها، ستون‌ها و جعبه‌ها، تعداد مقایسه‌ها کاهش می‌یابد و زمان اجرای الگوریتم حل سودوکو به طور قابل توجهی بهبود می‌یابد. این تکنیک باعث می‌شود تا فضای مورد نیاز برای ذخیره‌سازی داده‌ها کاهش یافته و عملکرد الگوریتم سریع‌تر شود.
مقدمه
سودوکو یک معمای محبوب و جذاب است که در یک جدول ۹×۹ با ۸۱ خانه قرار دارد و هدف آن پر کردن خانه‌ها با اعدادی از ۱ تا ۹ است به طوری که هیچ عددی در هر ردیف، ستون و جعبه ۳×۳ تکرار نشود. این معما با داشتن قوانینی ساده، چالشی پیچیده برای حل‌کنندگان ایجاد می‌کند و در عین حال ابزارهای مختلفی برای حل آن وجود دارد. سودوکو نه تنها به عنوان یک بازی سرگرم‌کننده شناخته می‌شود، بلکه به عنوان موضوعی برای تحقیقات علمی و الگوریتم‌های کامپیوتری مورد توجه قرار گرفته است.
قوانین سودوکو
یک الگوریتم حل سودوکو باید قوانین زیر را رعایت کند:
- هر عدد از ۱ تا ۹ باید دقیقاً یک بار در هر سطر ظاهر شود.
- هر عدد از ۱ تا ۹ باید دقیقاً یک بار در هر ستون ظاهر شود.
- هر عدد از ۱ تا ۹ باید دقیقاً یک بار در هر زیرماتریس ۳×۳ تکرار شود.
توجه: در ماتریس اولیه، خانه‌های خالی با مقدار صفر مشخص شده‌اند و تنها این خانه‌ها باید با اعداد ۱ تا ۹ پر شوند. مقدار اولیه سایر خانه‌ها نباید تغییر کند.
مثال
ورودی: (یک مثال از سودوکو که برخی از خانه‌های آن خالی هستند.)
خروجی: (ماتریسی که الگوریتم حل سودوکو به درستی آن را تکمیل کرده است.)
توضیح: در خروجی، تمامی سطرها، ستون‌ها و زیرماتریس‌های ۳×۳ دارای اعداد منحصر‌به‌فرد هستند.
روش‌های الگوریتم حل سودوکو
حل مسئله سودوکو با الگوریتم‌های مختلفی امکان‌پذیر است. برخی از روش‌های رایج عبارت‌اند از:
الگوریتم حل سودوکو با استفاده از بازگشت (Backtracking)
یک روش ساده اما مؤثر برای پیاده‌سازی الگوریتم حل سودوکو، استفاده از بازگشت است. در این روش:
- هر خانه خالی از ماتریس را بررسی می‌کنیم.
- اعداد ۱ تا ۹ را به ترتیب در این خانه قرار می‌دهیم و بررسی می‌کنیم که آیا عدد قرار داده‌شده معتبر است یا خیر.
- در صورتی که مقدار قرار داده‌شده معتبر باشد، به خانه بعدی می‌رویم. در غیر این صورت، مقدار را تغییر داده و مجدداً بررسی می‌کنیم.
- اگر هیچ عددی بین ۱ تا ۹ معتبر نبود، به خانه قبلی بازگشته و مقدار جدیدی امتحان می‌کنیم (Backtracking).
این الگوریتم با بررسی هر خانه به طور دنباله‌وار و تست مقادیر مختلف، در نهایت به یک راه‌حل قطعی دست می‌یابد. الگوریتم بازگشت به عقب از آن جهت محبوب است که به صورت تضمینی یک راه‌حل پیدا می‌کند، اگر معما معتبر باشد، اما در برخی موارد زمان‌بر است.
برنامه ++C برای حل سودوکو با روش بازگشت
// C++ Program to solve Sudoku problem
#include <iostream>
#include <vector>
using namespace std;
// Function to check if it is safe to place num at mat[row][col]
bool isSafe(vector<vector<int>> &mat, int row, int col, int num) {
// Check if num exist in the row
for (int x = 0; x <= 8; x++)
if (mat[row][x] == num)
return false;
// Check if num exist in the col
for (int x = 0; x <= 8; x++)
if (mat[x][col] == num)
return false;
// Check if num exist in the 3x3 sub-matrix
int startRow = row - (row % 3), startCol = col - (col % 3);
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (mat[i + startRow][j + startCol] == num)
return false;
return true;
}
// Function to solve the Sudoku problem
bool solveSudokuRec(vector<vector<int>> &mat, int row, int col) {
int n = mat.size();
// base case: Reached nth column of last row
if (row == n - 1 && col == n)
return true;
// If last column of the row go to next row
if (col == n) {
row++;
col = 0;
}
// If cell is already occupied then move forward
if (mat[row][col] != 0)
return solveSudokuRec(mat, row, col + 1);
for (int num = 1; num <= n; num++) {
// If it is safe to place num at current position
if (isSafe(mat, row, col, num)) {
mat[row][col] = num;
if (solveSudokuRec(mat, row, col + 1))
return true;
mat[row][col] = 0;
}
}
return false;
}
void solveSudoku(vector<vector<int>> &mat) {
solveSudokuRec(mat, 0, 0);
}
int main() {
vector<vector<int>> mat = {
{۳, ۰, ۶, ۵, ۰, ۸, ۴, ۰, ۰},
{۵, ۲, ۰, ۰, ۰, ۰, ۰, ۰, ۰},
{۰, ۸, ۷, ۰, ۰, ۰, ۰, ۳, ۱},
{۰, ۰, ۳, ۰, ۱, ۰, ۰, ۸, ۰},
{۹, ۰, ۰, ۸, ۶, ۳, ۰, ۰, ۵},
{۰, ۵, ۰, ۰, ۹, ۰, ۶, ۰, ۰},
{۱, ۳, ۰, ۰, ۰, ۰, ۲, ۵, ۰},
{۰, ۰, ۰, ۰, ۰, ۰, ۰, ۷, ۴},
{۰, ۰, ۵, ۲, ۰, ۶, ۳, ۰, ۰}};
solveSudoku(mat);
for (int i = 0; i < mat.size(); i++) {
for (int j = 0; j < mat.size(); j++)
cout << mat[i][j] << " ";
cout << endl;
}
return 0;
}
برنامه سی شارپ #C برای حل سودوکو با روش بازگشت
// C# Program to solve Sudoku problem
using System;
class PStore
{
// Function to check if it is safe to place num at mat[row][col]
static bool isSafe(int[,] mat, int row, int col, int num)
{
// Check if num exists in the row
for (int x = 0; x < 9; x++)
if (mat[row, x] == num)
return false;
// Check if num exists in the col
for (int x = 0; x < 9; x++)
if (mat[x, col] == num)
return false;
// Check if num exists in the 3x3 sub-matrix
int startRow = row - (row % 3), startCol = col - (col % 3);
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (mat[i + startRow, j + startCol] == num)
return false;
return true;
}
// Function to solve the Sudoku problem
static bool solveSudokuRec(int[,] mat, int row, int col) {
// base case: Reached nth column of the last row
if (row == 8 && col == 9)
return true;
// If last column of the row go to the next row
if (col == 9) {
row++;
col = 0;
}
// If cell is already occupied then move forward
if (mat[row, col] != 0)
return solveSudokuRec(mat, row, col + 1);
for (int num = 1; num <= 9; num++) {
// If it is safe to place num at current position
if (isSafe(mat, row, col, num)) {
mat[row, col] = num;
if (solveSudokuRec(mat, row, col + 1))
return true;
mat[row, col] = 0;
}
}
return false;
}
static void solveSudoku(int[,] mat) {
solveSudokuRec(mat, 0, 0);
}
public static void Main() {
int[,] mat = {
{۳, ۰, ۶, ۵, ۰, ۸, ۴, ۰, ۰},
{۵, ۲, ۰, ۰, ۰, ۰, ۰, ۰, ۰},
{۰, ۸, ۷, ۰, ۰, ۰, ۰, ۳, ۱},
{۰, ۰, ۳, ۰, ۱, ۰, ۰, ۸, ۰},
{۹, ۰, ۰, ۸, ۶, ۳, ۰, ۰, ۵},
{۰, ۵, ۰, ۰, ۹, ۰, ۶, ۰, ۰},
{۱, ۳, ۰, ۰, ۰, ۰, ۲, ۵, ۰},
{۰, ۰, ۰, ۰, ۰, ۰, ۰, ۷, ۴},
{۰, ۰, ۵, ۲, ۰, ۶, ۳, ۰, ۰}
};
solveSudoku(mat);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
Console.Write(mat[i, j] + " ");
Console.WriteLine();
}
}
}
برنامه جاوا برای حل سودوکو
// Java Program to solve Sudoku problem
import java.util.Arrays;
class PStore
{
// Function to check if it is safe to place num at mat[row][col]
static boolean isSafe(int[][] mat, int row, int col, int num)
{
// Check if num exists in the row
for (int x = 0; x < 9; x++)
if (mat[row][x] == num)
return false;
// Check if num exists in the col
for (int x = 0; x < 9; x++)
if (mat[x][col] == num)
return false;
// Check if num exists in the 3x3 sub-matrix
int startRow = row - (row % 3), startCol = col - (col % 3);
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (mat[i + startRow][j + startCol] == num)
return false;
return true;
}
// Function to solve the Sudoku problem
static boolean solveSudokuRec(int[][] mat, int row, int col) {
// base case: Reached nth column of the last row
if (row == 8 && col == 9)
return true;
// If last column of the row go to the next row
if (col == 9) {
row++;
col = 0;
}
// If cell is already occupied then move forward
if (mat[row][col] != 0)
return solveSudokuRec(mat, row, col + 1);
for (int num = 1; num <= 9; num++) {
// If it is safe to place num at current position
if (isSafe(mat, row, col, num)) {
mat[row][col] = num;
if (solveSudokuRec(mat, row, col + 1))
return true;
mat[row][col] = 0;
}
}
return false;
}
static void solveSudoku(int[][] mat) {
solveSudokuRec(mat, 0, 0);
}
public static void main(String[] args) {
int[][] mat = {
{۳, ۰, ۶, ۵, ۰, ۸, ۴, ۰, ۰},
{۵, ۲, ۰, ۰, ۰, ۰, ۰, ۰, ۰},
{۰, ۸, ۷, ۰, ۰, ۰, ۰, ۳, ۱},
{۰, ۰, ۳, ۰, ۱, ۰, ۰, ۸, ۰},
{۹, ۰, ۰, ۸, ۶, ۳, ۰, ۰, ۵},
{۰, ۵, ۰, ۰, ۹, ۰, ۶, ۰, ۰},
{۱, ۳, ۰, ۰, ۰, ۰, ۲, ۵, ۰},
{۰, ۰, ۰, ۰, ۰, ۰, ۰, ۷, ۴},
{۰, ۰, ۵, ۲, ۰, ۶, ۳, ۰, ۰}
};
solveSudoku(mat);
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[i].length; j++)
System.out.print(mat[i][j] + " ");
System.out.println();
}
}
}
برنامه پایتون برای حل سودوکو
# Python Program to solve Sudoku problem
# Function to check if it is safe to place num at mat[row][col]
def isSafe(mat, row, col, num):
# Check if num exists in the row
for x in range(9):
if mat[row][x] == num:
return False
# Check if num exists in the col
for x in range(9):
if mat[x][col] == num:
return False
# Check if num exists in the 3x3 sub-matrix
startRow = row - (row % 3)
startCol = col - (col % 3)
for i in range(3):
for j in range(3):
if mat[i + startRow][j + startCol] == num:
return False
return True
# Function to solve the Sudoku problem
def solveSudokuRec(mat, row, col):
# base case: Reached nth column of the last row
if row == 8 and col == 9:
return True
# If last column of the row go to the next row
if col == 9:
row += 1
col = 0
# If cell is already occupied then move forward
if mat[row][col] != 0:
return solveSudokuRec(mat, row, col + 1)
for num in range(1, 10):
# If it is safe to place num at current position
if isSafe(mat, row, col, num):
mat[row][col] = num
if solveSudokuRec(mat, row, col + 1):
return True
mat[row][col] = 0
return False
def solveSudoku(mat):
solveSudokuRec(mat, 0, 0)
if __name__ == "__main__":
mat = [
[۳, ۰, ۶, ۵, ۰, ۸, ۴, ۰, ۰],
[۵, ۲, ۰, ۰, ۰, ۰, ۰, ۰, ۰],
[۰, ۸, ۷, ۰, ۰, ۰, ۰, ۳, ۱],
[۰, ۰, ۳, ۰, ۱, ۰, ۰, ۸, ۰],
[۹, ۰, ۰, ۸, ۶, ۳, ۰, ۰, ۵],
[۰, ۵, ۰, ۰, ۹, ۰, ۶, ۰, ۰],
[۱, ۳, ۰, ۰, ۰, ۰, ۲, ۵, ۰],
[۰, ۰, ۰, ۰, ۰, ۰, ۰, ۷, ۴],
[۰, ۰, ۵, ۲, ۰, ۶, ۳, ۰, ۰]
]
solveSudoku(mat)
for row in mat:
print(" ".join(map(str, row)))
برنامه جاوا اسکریپت برای حل سودوکو
// JavaScript Program to solve Sudoku problem
// Function to check if it is safe to place num at mat[row][col]
function isSafe(mat, row, col, num) {
// Check if num exists in the row
for (let x = 0; x < 9; x++)
if (mat[row][x] === num)
return false;
// Check if num exists in the col
for (let x = 0; x < 9; x++)
if (mat[x][col] === num)
return false;
// Check if num exists in the 3x3 sub-matrix
const startRow = row - (row % 3),
startCol = col - (col % 3);
for (let i = 0; i < 3; i++)
for (let j = 0; j < 3; j++)
if (mat[i + startRow][j + startCol] === num)
return false;
return true;
}
// Function to solve the Sudoku problem
function solveSudokuRec(mat, row, col) {
// base case: Reached nth column of the last row
if (row === 8 && col === 9)
return true;
// If last column of the row go to the next row
if (col === 9) {
row++;
col = 0;
}
// If cell is already occupied then move forward
if (mat[row][col] !== 0)
return solveSudokuRec(mat, row, col + 1);
for (let num = 1; num <= 9; num++) {
// If it is safe to place num at current position
if (isSafe(mat, row, col, num)) {
mat[row][col] = num;
if (solveSudokuRec(mat, row, col + 1))
return true;
mat[row][col] = 0;
}
}
return false;
}
function solveSudoku(mat) {
solveSudokuRec(mat, 0, 0);
}
// Driver Code
const mat = [
[۳, ۰, ۶, ۵, ۰, ۸, ۴, ۰, ۰],
[۵, ۲, ۰, ۰, ۰, ۰, ۰, ۰, ۰],
[۰, ۸, ۷, ۰, ۰, ۰, ۰, ۳, ۱],
[۰, ۰, ۳, ۰, ۱, ۰, ۰, ۸, ۰],
[۹, ۰, ۰, ۸, ۶, ۳, ۰, ۰, ۵],
[۰, ۵, ۰, ۰, ۹, ۰, ۶, ۰, ۰],
[۱, ۳, ۰, ۰, ۰, ۰, ۲, ۵, ۰],
[۰, ۰, ۰, ۰, ۰, ۰, ۰, ۷, ۴],
[۰, ۰, ۵, ۲, ۰, ۶, ۳, ۰, ۰]
];
solveSudoku(mat);
mat.forEach(row => console.log(row.join(" ")));
خروجی
۳ ۱ ۶ ۵ ۷ ۸ ۴ ۹ ۲ ۵ ۲ ۹ ۱ ۳ ۴ ۷ ۶ ۸ ۴ ۸ ۷ ۶ ۲ ۹ ۵ ۳ ۱ ۲ ۶ ۳ ۴ ۱ ۵ ۹ ۸ ۷ ۹ ۷ ۴ ۸ ۶ ۳ ۱ ۲ ۵ ۸ ۵ ۱ ۷ ۹ ۲ ۶ ۴ ۳ ۱ ۳ ۸ ۹ ۴ ۷ ۲ ۵ ۶ ۶ ۹ ۲ ۳ ۵ ۱ ۸ ۷ ۴ ۷ ۴ ۵ ۲ ۸ ۶ ۳ ۱ ۹
پیچیدگی زمانی و فضایی روش بازگشت:
پیچیدگی زمانی: O(n*9(n*n)) به این دلیل که برای هر خانه خالی، ۹ مقدار ممکن وجود دارد و برای هر مقدار، سطر، ستون و زیرماتریس ۳×۳ بررسی می‌شود.
فضای کمکی: O(1)، زیرا فضای اضافی زیادی مصرف نمی‌شود.
الگوریتم حل سودوکو با استفاده از ماسک بیت
یک راه‌حل پیشرفته‌تر برای بهینه‌سازی الگوریتم حل سودوکو، استفاده از ماسک بیت است. در روش اولیه، برای الگوریتم حل سودوکو، تابع ()isSafe بررسی می‌کند که آیا قرار دادن عدد num در خانه (i, j) مجاز است یا خیر. این بررسی در روش‌های معمولی با جستجو در کل سطر، ستون و زیرماتریس ۳×۳ انجام می‌شود که زمان‌بر است. برای بهینه‌سازی این فرایند، از ماسک بیت «Bit Masking» استفاده می‌کنیم.به‌جای جستجوی خطی در سطرها، ستون‌ها و زیرماتریس‌ها، سه آرایه زیر تعریف می‌کنیم:
- []rows : وضعیت استفاده از اعداد در هر سطر را مشخص می‌کند.
- []cols : وضعیت استفاده از اعداد در هر ستون را مشخص می‌کند.
- []boxs : وضعیت استفاده از اعداد در هر زیرماتریس ۳×۳ را مشخص می‌کند.
نحوه عملکرد:
- اگر عدد num در سطر i استفاده شده باشد، بیت مربوط به num در rows[i] تنظیم می‌شود.
- اگر عدد num در ستون j استفاده شده باشد، بیت مربوطه در cols[j] تنظیم می‌شود.
- اگر عدد num در زیرماتریس مربوط به (i, j) استفاده شده باشد، بیت مربوط به num در boxs[k] (که k شماره زیرماتریس را نشان می‌دهد) تنظیم می‌شود.
- برای بررسی امکان قرار دادن یک مقدار، کافی است از عملگرهای AND و OR بیت‌وایز استفاده کنیم تا ببینیم آیا بیت مربوطه قبلاً تنظیم شده است یا نه.
- برای حذف یک مقدار، از عملگرهای حذف بیت (Bit Unset) استفاده می‌شود.
برنامه ++C برای حل سودوکو با روش ماسک بیت
// C++ Program to solve Sudoku problem
#include <iostream>
#include <vector>
using namespace std;
// Function to heck if it is safe to place num at mat[row][col]
bool isSafe(vector<vector<int>> &mat, int i, int j, int num,
vector<int> &row, vector<int> &col, vector<int> &box) {
if( (row[i] & (1 << num)) || (col[j] & (1 << num)) ||
(box[i / 3 * 3 + j / 3] & (1 << num)) )
return false;
return true;
}
bool sudokuSolverRec(vector<vector<int>> &mat, int i, int j,
vector<int> &row, vector<int> &col, vector<int> &box) {
int n = mat.size();
// base case: Reached nth column of last row
if (i == n - 1 && j == n)
return true;
// If reached last column of the row go to next row
if (j == n) {
i++;
j = 0;
}
// If cell is already occupied then move forward
if (mat[i][j] != 0)
return sudokuSolverRec(mat, i, j + 1, row, col, box);
for (int num = 1; num <= n; num++) {
// If it is safe to place num at current position
if (isSafe(mat, i, j, num, row, col, box)) {
mat[i][j] = num;
// Update masks for the corresponding row, column and box
row[i] |= (1 << num);
col[j] |= (1 << num);
box[i / 3 * 3 + j / 3] |= (1 << num);
if (sudokuSolverRec(mat, i, j + 1, row, col, box))
return true;
// Unmask the number num in the corresponding row, column and box masks
mat[i][j] = 0;
row[i] &= ~(1 << num);
col[j] &= ~(1 << num);
box[i / 3 * 3 + j / 3] &= ~(1 << num);
}
}
return false;
}
void solveSudoku(vector<vector<int>> &mat) {
int n = mat.size();
vector<int> row(n, 0), col(n, 0), box(n, 0);
// Set the bits in bitmasks for values that are initital present
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] != 0) {
row[i] |= (1 << mat[i][j]);
col[j] |= (1 << mat[i][j]);
box[ (i / 3) * 3 + j / 3] |= (1 << mat[i][j]);
}
}
}
sudokuSolverRec(mat, 0, 0, row, col, box);
}
int main() {
vector<vector<int>> mat = {
{۳, ۰, ۶, ۵, ۰, ۸, ۴, ۰, ۰},
{۵, ۲, ۰, ۰, ۰, ۰, ۰, ۰, ۰},
{۰, ۸, ۷, ۰, ۰, ۰, ۰, ۳, ۱},
{۰, ۰, ۳, ۰, ۱, ۰, ۰, ۸, ۰},
{۹, ۰, ۰, ۸, ۶, ۳, ۰, ۰, ۵},
{۰, ۵, ۰, ۰, ۹, ۰, ۶, ۰, ۰},
{۱, ۳, ۰, ۰, ۰, ۰, ۲, ۵, ۰},
{۰, ۰, ۰, ۰, ۰, ۰, ۰, ۷, ۴},
{۰, ۰, ۵, ۲, ۰, ۶, ۳, ۰, ۰}};
solveSudoku(mat);
for (int i = 0; i < mat.size(); i++) {
for (int j = 0; j < mat.size(); j++)
cout << mat[i][j] << " ";
cout << endl;
}
return 0;
}
برنامه سی شارپ برای حل سودوکو
// C# Program to solve Sudoku problem using bitmasks
using System;
class PStore
{
// Function to check if it is safe to place num at mat[row, col]
static bool isSafe(int[,] mat, int i, int j, int num,
int[] row, int[] col, int[] box) {
if ((row[i] & (1 << num)) != 0 || (col[j] & (1 << num)) != 0 ||
(box[i / 3 * 3 + j / 3] & (1 << num)) != 0)
return false;
return true;
}
static bool sudokuSolverRec(int[,] mat, int i, int j,
int[] row, int[] col, int[] box) {
int n = mat.GetLength(0);
// base case: Reached nth column of last row
if (i == n - 1 && j == n)
return true;
// If reached last column of the row, go to next row
if (j == n) {
i++;
j = 0;
}
// If cell is already occupied, then move forward
if (mat[i, j] != 0)
return sudokuSolverRec(mat, i, j + 1, row, col, box);
for (int num = 1; num <= n; num++) {
// If it is safe to place num at current position
if (isSafe(mat, i, j, num, row, col, box)) {
mat[i, j] = num;
// Update masks for the corresponding row, column, and box
row[i] |= (1 << num);
col[j] |= (1 << num);
box[i / 3 * 3 + j / 3] |= (1 << num);
if (sudokuSolverRec(mat, i, j + 1, row, col, box))
return true;
// Unmask the number num in the corresponding row, column and box masks
mat[i, j] = 0;
row[i] &= ~(1 << num);
col[j] &= ~(1 << num);
box[i / 3 * 3 + j / 3] &= ~(1 << num);
}
}
return false;
}
static void solveSudoku(int[,] mat) {
int n = mat.GetLength(0);
int[] row = new int[n];
int[] col = new int[n];
int[] box = new int[n];
// Set the bits in bitmasks for values that are initially present
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mat[i, j] != 0) {
row[i] |= (1 << mat[i, j]);
col[j] |= (1 << mat[i, j]);
box[(i / 3) * 3 + j / 3] |= (1 << mat[i, j]);
}
}
}
sudokuSolverRec(mat, 0, 0, row, col, box);
}
public static void Main(string[] args) {
int[,] mat = {
{۳, ۰, ۶, ۵, ۰, ۸, ۴, ۰, ۰},
{۵, ۲, ۰, ۰, ۰, ۰, ۰, ۰, ۰},
{۰, ۸, ۷, ۰, ۰, ۰, ۰, ۳, ۱},
{۰, ۰, ۳, ۰, ۱, ۰, ۰, ۸, ۰},
{۹, ۰, ۰, ۸, ۶, ۳, ۰, ۰, ۵},
{۰, ۵, ۰, ۰, ۹, ۰, ۶, ۰, ۰},
{۱, ۳, ۰, ۰, ۰, ۰, ۲, ۵, ۰},
{۰, ۰, ۰, ۰, ۰, ۰, ۰, ۷, ۴},
{۰, ۰, ۵, ۲, ۰, ۶, ۳, ۰, ۰}
};
solveSudoku(mat);
for (int i = 0; i < mat.GetLength(0); i++) {
for (int j = 0; j < mat.GetLength(1); j++)
Console.Write(mat[i, j] + " ");
Console.WriteLine();
}
}
}
برنامه جاوا برای حل سودوکو
// Java Program to solve Sudoku problem
import java.util.Arrays;
class PStore
{
// Function to check if it is safe to place num at mat[row][col]
static boolean isSafe(int[][] mat, int i, int j, int num,
int[] row, int[] col, int[] box) {
if ((row[i] & (1 << num)) != 0 || (col[j] & (1 << num)) != 0 ||
(box[i / 3 * 3 + j / 3] & (1 << num)) != 0)
return false;
return true;
}
static boolean sudokuSolverRec(int[][] mat, int i, int j,
int[] row, int[] col, int[] box) {
int n = mat.length;
// base case: Reached nth column of last row
if (i == n - 1 && j == n)
return true;
// If reached last column of the row go to next row
if (j == n) {
i++;
j = 0;
}
// If cell is already occupied then move forward
if (mat[i][j] != 0)
return sudokuSolverRec(mat, i, j + 1, row, col, box);
for (int num = 1; num <= n; num++) {
// If it is safe to place num at current position
if (isSafe(mat, i, j, num, row, col, box)) {
mat[i][j] = num;
// Update masks for the corresponding row, column and box
row[i] |= (1 << num);
col[j] |= (1 << num);
box[i / 3 * 3 + j / 3] |= (1 << num);
if (sudokuSolverRec(mat, i, j + 1, row, col, box))
return true;
// Unmask the number num in the corresponding row, column and box masks
mat[i][j] = 0;
row[i] &= ~(1 << num);
col[j] &= ~(1 << num);
box[i / 3 * 3 + j / 3] &= ~(1 << num);
}
}
return false;
}
static void solveSudoku(int[][] mat) {
int n = mat.length;
int[] row = new int[n];
int[] col = new int[n];
int[] box = new int[n];
// Set the bits in bitmasks for values that are initially present
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] != 0) {
row[i] |= (1 << mat[i][j]);
col[j] |= (1 << mat[i][j]);
box[(i / 3) * 3 + j / 3] |= (1 << mat[i][j]);
}
}
}
sudokuSolverRec(mat, 0, 0, row, col, box);
}
public static void main(String[] args) {
int[][] mat = {
{۳, ۰, ۶, ۵, ۰, ۸, ۴, ۰, ۰},
{۵, ۲, ۰, ۰, ۰, ۰, ۰, ۰, ۰},
{۰, ۸, ۷, ۰, ۰, ۰, ۰, ۳, ۱},
{۰, ۰, ۳, ۰, ۱, ۰, ۰, ۸, ۰},
{۹, ۰, ۰, ۸, ۶, ۳, ۰, ۰, ۵},
{۰, ۵, ۰, ۰, ۹, ۰, ۶, ۰, ۰},
{۱, ۳, ۰, ۰, ۰, ۰, ۲, ۵, ۰},
{۰, ۰, ۰, ۰, ۰, ۰, ۰, ۷, ۴},
{۰, ۰, ۵, ۲, ۰, ۶, ۳, ۰, ۰}
};
solveSudoku(mat);
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[i].length; j++)
System.out.print(mat[i][j] + " ");
System.out.println();
}
}
}
برنامه پایتون برای حل سودوکو
# Python Program to solve Sudoku problem
def isSafe(mat, i, j, num, row, col, box):
if (row[i] & (1 << num)) or (col[j] & (1 << num)) or (box[i // 3 * 3 + j // 3] & (1 << num)):
return False
return True
def sudokuSolverRec(mat, i, j, row, col, box):
n = len(mat)
# base case: Reached nth column of last row
if i == n - 1 and j == n:
return True
# If reached last column of the row go to next row
if j == n:
i += 1
j = 0
# If cell is already occupied then move forward
if mat[i][j] != 0:
return sudokuSolverRec(mat, i, j + 1, row, col, box)
for num in range(1, n + 1):
# If it is safe to place num at current position
if isSafe(mat, i, j, num, row, col, box):
mat[i][j] = num
# Update masks for the corresponding row, column and box
row[i] |= (1 << num)
col[j] |= (1 << num)
box[i // 3 * 3 + j // 3] |= (1 << num)
if sudokuSolverRec(mat, i, j + 1, row, col, box):
return True
# Unmask the number num in the corresponding row, column and box masks
mat[i][j] = 0
row[i] &= ~(1 << num)
col[j] &= ~(1 << num)
box[i // 3 * 3 + j // 3] &= ~(1 << num)
return False
def solveSudoku(mat):
n = len(mat)
row = [0] * n
col = [0] * n
box = [0] * n
# Set the bits in bitmasks for values that are initially present
for i in range(n):
for j in range(n):
if mat[i][j] != 0:
row[i] |= (1 << mat[i][j])
col[j] |= (1 << mat[i][j])
box[(i // 3) * 3 + j // 3] |= (1 << mat[i][j])
sudokuSolverRec(mat, 0, 0, row, col, box)
if __name__ == "__main__":
mat = [
[۳, ۰, ۶, ۵, ۰, ۸, ۴, ۰, ۰],
[۵, ۲, ۰, ۰, ۰, ۰, ۰, ۰, ۰],
[۰, ۸, ۷, ۰, ۰, ۰, ۰, ۳, ۱],
[۰, ۰, ۳, ۰, ۱, ۰, ۰, ۸, ۰],
[۹, ۰, ۰, ۸, ۶, ۳, ۰, ۰, ۵],
[۰, ۵, ۰, ۰, ۹, ۰, ۶, ۰, ۰],
[۱, ۳, ۰, ۰, ۰, ۰, ۲, ۵, ۰],
[۰, ۰, ۰, ۰, ۰, ۰, ۰, ۷, ۴],
[۰, ۰, ۵, ۲, ۰, ۶, ۳, ۰, ۰]
]
solveSudoku(mat)
for row in mat:
print(" ".join(map(str, row)))
برنامه جاوا اسکریپت برای حل سودوکو
// JavaScript Program to solve Sudoku problem using bitmasks
// Function to check if it is safe to place num at mat[row][col]
function isSafe(mat, i, j, num, row, col, box) {
if ((row[i] & (1 << num)) !== 0 || (col[j] & (1 << num)) !== 0 ||
(box[Math.floor(i / 3) * 3 + Math.floor(j / 3)] & (1 << num)) !== 0)
return false;
return true;
}
function sudokuSolverRec(mat, i, j, row, col, box) {
const n = mat.length;
// base case: Reached nth column of last row
if (i === n - 1 && j === n)
return true;
// If reached last column of the row, go to next row
if (j === n) {
i++;
j = 0;
}
// If cell is already occupied, then move forward
if (mat[i][j] !== 0)
return sudokuSolverRec(mat, i, j + 1, row, col, box);
for (let num = 1; num <= n; num++) {
// If it is safe to place num at current position
if (isSafe(mat, i, j, num, row, col, box)) {
mat[i][j] = num;
// Update masks for the corresponding row, column, and box
row[i] |= (1 << num);
col[j] |= (1 << num);
box[Math.floor(i / 3) * 3 + Math.floor(j / 3)] |= (1 << num);
if (sudokuSolverRec(mat, i, j + 1, row, col, box))
return true;
// Unmask the number num in the corresponding row, column and box masks
mat[i][j] = 0;
row[i] &= ~(1 << num);
col[j] &= ~(1 << num);
box[Math.floor(i / 3) * 3 + Math.floor(j / 3)] &= ~(1 << num);
}
}
return false;
}
function solveSudoku(mat) {
const n = mat.length;
const row = new Array(n).fill(0);
const col = new Array(n).fill(0);
const box = new Array(n).fill(0);
// Set the bits in bitmasks for values that are initially present
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (mat[i][j] !== 0) {
row[i] |= (1 << mat[i][j]);
col[j] |= (1 << mat[i][j]);
box[Math.floor(i / 3) * 3 + Math.floor(j / 3)] |= (1 << mat[i][j]);
}
}
}
sudokuSolverRec(mat, 0, 0, row, col, box);
}
// Driver Code
const mat = [
[۳, ۰, ۶, ۵, ۰, ۸, ۴, ۰, ۰],
[۵, ۲, ۰, ۰, ۰, ۰, ۰, ۰, ۰],
[۰, ۸, ۷, ۰, ۰, ۰, ۰, ۳, ۱],
[۰, ۰, ۳, ۰, ۱, ۰, ۰, ۸, ۰],
[۹, ۰, ۰, ۸, ۶, ۳, ۰, ۰, ۵],
[۰, ۵, ۰, ۰, ۹, ۰, ۶, ۰, ۰],
[۱, ۳, ۰, ۰, ۰, ۰, ۲, ۵, ۰],
[۰, ۰, ۰, ۰, ۰, ۰, ۰, ۷, ۴],
[۰, ۰, ۵, ۲, ۰, ۶, ۳, ۰, ۰]
];
solveSudoku(mat);
for (let i = 0; i < mat.length; i++) {
console.log(mat[i].join(" "));
}
خروجی
۳ ۱ ۶ ۵ ۷ ۸ ۴ ۹ ۲ ۵ ۲ ۹ ۱ ۳ ۴ ۷ ۶ ۸ ۴ ۸ ۷ ۶ ۲ ۹ ۵ ۳ ۱ ۲ ۶ ۳ ۴ ۱ ۵ ۹ ۸ ۷ ۹ ۷ ۴ ۸ ۶ ۳ ۱ ۲ ۵ ۸ ۵ ۱ ۷ ۹ ۲ ۶ ۴ ۳ ۱ ۳ ۸ ۹ ۴ ۷ ۲ ۵ ۶ ۶ ۹ ۲ ۳ ۵ ۱ ۸ ۷ ۴ ۷ ۴ ۵ ۲ ۸ ۶ ۳ ۱ ۹
پیچیدگی زمانی و فضایی روش ماسک بیت:
پیچیدگی زمانی: O(9(n*n)) که بهینه‌تر از روش بازگشتی ساده است.
فضای کمکی: O(n)، زیرا از چند آرایه اضافی برای بررسی مقادیر استفاده می‌شود.
مزیت‌های روش ماسک بیت
- به جای جستجوی خطی در هر سطر، ستون و جعبه، تنها یک عملیات بیت‌وایز انجام می‌شود که بسیار سریع‌تر است.
- پیچیدگی زمانی کاهش یافته و اجرای الگوریتم حل سودوکو بهینه‌تر شده است.
- فضای مورد نیاز به O(n) محدود شده و نیازی به ذخیره‌سازی ماتریس اضافی نیست.
- این روش به‌عنوان یک الگوریتم حل سودوکو کارآمد، عملکرد بالایی دارد و در حل پازل‌های سودوکو با داده‌های حجیم نیز مؤثر خواهد بود.
نتیجه‌گیری
در این مقاله، روش‌های مختلفی برای پیاده‌سازی الگوریتم حل سودوکو بررسی شد. ابتدا روش بازگشتی ارائه شد که ساده و کاربردی است اما دارای پیچیدگی زمانی بالاست. سپس، رویکرد بهینه‌تری با استفاده از ماسک بیت معرفی شد که اجرای سریع‌تر و کارآمدتری را برای الگوریتم حل سودوکو فراهم می‌کند.
با استفاده از این الگوریتم‌های بهینه‌شده، می‌توان مسائل پیچیده‌تر مرتبط با سودوکو را با سرعت بیشتری حل کرد. این روش‌ها نه‌تنها برای حل سودوکو بلکه در سایر مسائل مرتبط با جستجو و بهینه‌سازی نیز قابل استفاده هستند.
