N-Queens Problem এবং Sudoku Solver উভয়ই কম্পিউটারে সমাধানযোগ্য জনপ্রিয় সমস্যাগুলির মধ্যে অন্যতম। উভয় সমস্যায় ব্যাকট্র্যাকিং কৌশল ব্যবহার করা হয়, যা সম্ভাব্য সমাধানের পথগুলো অন্বেষণ করে নির্দিষ্ট শর্ত মেনে সমাধান খুঁজে বের করে।
১. N-Queens Problem
N-Queens Problem হলো এমন একটি সমস্যা যেখানে N x N চেস বোর্ডে N সংখ্যক কুইন রাখা হয় এবং প্রতিটি কুইন এমনভাবে স্থাপন করতে হয় যাতে তারা একে অপরকে আক্রমণ করতে না পারে। অর্থাৎ কোনো দুই কুইন একই সারি, কলাম, বা তির্যক লাইনে অবস্থান করতে পারবে না।
উদাহরণ
ধরুন N = 4 অর্থাৎ, 4x4 বোর্ডে ৪টি কুইন এমনভাবে রাখতে হবে যাতে তারা কেউ কাউকে আক্রমণ করতে না পারে। একটি সম্ভাব্য সমাধান হতে পারে:
. Q . .
. . . Q
Q . . .
. . Q .
সমাধান পদ্ধতি
এই সমস্যার সমাধানে ব্যাকট্র্যাকিং ব্যবহার করা হয়। আমরা প্রতিটি সারিতে একটি করে কুইন স্থাপন করে সম্ভাব্য অবস্থানগুলো পরীক্ষা করি এবং যদি কোনো অবস্থান শর্ত মেনে না চলে, তাহলে আগের ধাপে ফিরে অন্য অবস্থান পরীক্ষা করি।
উদাহরণ কোড (Python):
def is_safe(board, row, col, N):
for i in range(row):
if board[i] == col or board[i] - i == col - row or board[i] + i == col + row:
return False
return True
def solve_n_queens(N):
board = [-1] * N
solutions = []
def place_queens(row):
if row == N:
solutions.append(["." * col + "Q" + "." * (N - col - 1) for col in board])
return
for col in range(N):
if is_safe(board, row, col, N):
board[row] = col
place_queens(row + 1)
board[row] = -1
place_queens(0)
return solutions
# উদাহরণ ব্যবহার
solutions = solve_n_queens(4)
for solution in solutions:
for line in solution:
print(line)
print()
টাইম এবং স্পেস কমপ্লেক্সিটি
- টাইম কমপ্লেক্সিটি: গড়ে O(N!), কারণ প্রতিটি সারিতে কুইন রাখার বিভিন্ন উপায় আছে।
- স্পেস কমপ্লেক্সিটি: O(N), কারণ বোর্ডের অবস্থা সংরক্ষণ করতে N সাইজের অ্যারে ব্যবহার করা হয়।
ব্যবহার
N-Queens Problem গেম থিওরি, কৌশলগত গেম এবং রোবোটিক্সে ট্রাফিক ম্যানেজমেন্ট ইত্যাদি ক্ষেত্রে প্রয়োগ করা হয়।
২. Sudoku Solver
Sudoku Solver একটি ব্যাকট্র্যাকিং সমস্যা, যেখানে 9x9 গ্রিডে ১-৯ সংখ্যাগুলি পূরণ করতে হয়। প্রতিটি সারি, কলাম, এবং ৩x৩ গ্রিডে প্রতিটি সংখ্যা একবার করে আসতে পারে।
উদাহরণ
ধরা যাক নিচের Sudoku বোর্ডটি পূরণ করতে হবে:
5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9
সমাধান পদ্ধতি
এই সমস্যার সমাধানে ব্যাকট্র্যাকিং ব্যবহার করা হয়। প্রথমে ফাঁকা স্থানগুলোতে সম্ভাব্য সংখ্যাগুলি বসানো হয়। প্রতিটি ফাঁকা স্থানে ১-৯ পর্যন্ত সংখ্যা বসিয়ে দেখা হয়, যদি এটি Sudoku নিয়ম মেনে চলে। যদি কোনো সংখ্যা বসানো সম্ভব না হয়, তাহলে আগের ধাপে ফিরে অন্য সংখ্যা পরীক্ষা করা হয়।
উদাহরণ কোড (Python):
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
return False
return True
def solve_sudoku(board):
for row in range(9):
for col in range(9):
if board[row][col] == 0:
for num in range(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
if solve_sudoku(board):
return True
board[row][col] = 0
return False
return True
# উদাহরণ ব্যবহার
sudoku_board = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
if solve_sudoku(sudoku_board):
for row in sudoku_board:
print(row)
else:
print("No solution exists")
টাইম এবং স্পেস কমপ্লেক্সিটি
- টাইম কমপ্লেক্সিটি: ব্যাকট্র্যাকিংয়ের জন্য গড়ে O(9^(n*n)), কারণ প্রতিটি ফাঁকা স্থানে ৯টি সম্ভাব্য সংখ্যা পরীক্ষা করতে হয়।
- স্পেস কমপ্লেক্সিটি: O(n*n), কারণ গ্রিডটি নিজেই অতিরিক্ত মেমোরি নেয়।
ব্যবহার
Sudoku Solver টেক্সট কমপ্লিশন, রিসোর্স শিডিউলিং এবং কৌশলগত গেম সমাধানে প্রায়ই ব্যবহৃত হয়।
উপসংহার
- N-Queens Problem কৌশলগত স্থান নির্ধারণের সমস্যা, যা ব্যাকট্র্যাকিং পদ্ধতিতে সহজে সমাধানযোগ্য।
- Sudoku Solver সংখ্যার গ্রিডে বিশেষ নিয়ম মেনে সমস্যা সমাধানে ব্যাকট্র্যাকিং ব্যবহার করে।
এ ধরনের সমস্যাগুলো আমাদের ব্যাকট্র্যাকিং কৌশল এবং দক্ষতার সাথে জটিল সমস্যার সমাধান খুঁজে বের করতে শেখায়।
