সুডোকু সমাধান অ্যালগরিদম

এই সেকশনে, আমরা বিখ্যাত নাম্বার মেজ সমস্যা সুডোকু সমাধান করার চেষ্টা করব। সুডোকু হলো একটি ৯ x ৯ নাম্বার গ্রিড, এবং পুরো গ্রিড ৩ x ৩ বক্সে ভাগ করা থাকে। সুডোকু সমাধানের কিছু নিয়ম আছে।

আমাদের ১ থেকে ৯ ডিজিট ব্যবহার করতে হবে এই সমস্যা সমাধানের জন্য।

একটি ডিজিট এক রো, এক কলাম বা এক ৩ x ৩ বক্সে রিপিট হতে পারবে না।

ব্যাকট্র্যাকিং অ্যালগরিদম ব্যবহার করে আমরা সুডোকু সমস্যা সমাধান করার চেষ্টা করব। যখন কোনো সেল একটি ডিজিট দিয়ে ফিল হয়, তখন চেক করা হয় সেটি বৈধ কিনা। যখন এটি বৈধ নয়, তবে অন্য নাম্বার চেক করা হয়। যদি ১-৯ সব নাম্বার চেক করা হয় এবং কোনো বৈধ ডিজিট পাওয়া যায় না রাখতে, তবে এটি ব্যাকট্র্যাক করে পূর্বের অপশনে চলে যায়।

ইনপুট এবং আউটপুট

ইনপুট: এটি একটি ৯ x ৯ ম্যাট্রিক্স নেবে সুডোকু গ্রিড হিসেবে। কিছু ভ্যালু গ্রিডে প্লেস করা থাকে। ব্ল্যাঙ্ক স্পেসগুলো ০ দিয়ে ডিনোট করা হয়।  আউটপুট: ফাইনাল ম্যাট্রিক্স (সুডোকু গ্রিড) নাম্বার দিয়ে ফিল্ড। যদি সমাধান এক্সিস্ট না করে, তবে false রিটার্ন করবে। 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

অ্যালগরিদম

isPresentInCol(col, num)

ইনপুট: কলাম, এবং টার্গেটেড নাম্বার।

আউটপুট - কলামে নাম্বার থাকলে True।

শুরু
  গ্রিডের প্রতিটি রো r-এর জন্য করুন
    যদি grid[r, col] = num, তবে
      return true
  শেষ
  অন্যথায় false রিটার্ন করুন
শেষ

isPresentInRow(row, num)

ইনপুট - রো, এবং টার্গেটেড নাম্বার।

আউটপুট - কলামে নাম্বার থাকলে True।

শুরু
  গ্রিডের প্রতিটি কলাম c-এর জন্য করুন
    যদি grid[row, c] = num, তবে
      return true
  শেষ
  অন্যথায় false রিটার্ন করুন
শেষ

isPresentInBox(boxStartRow, boxStartCol, num)

ইনপুট - ৩ x ৩ বক্সের শুরুর রো এবং কলাম, এবং টার্গেটেড নাম্বার।

আউটপুট - বক্সে নাম্বার থাকলে True।

শুরু
  বক্সের প্রতিটি রো r boxStartRow থেকে পরের ৩ রো পর্যন্ত, করুন
    বক্সের প্রতিটি কলাম c boxStartCol থেকে পরের ৩ কলাম পর্যন্ত, করুন
      যদি grid[r, c] = num, তবে
        return true
      শেষ
    শেষ
  অন্যথায় false রিটার্ন করুন
শেষ

findEmptyPlace(row, col)

ইনপুট: গ্রিডের রো এবং কলাম।

আউটপুট - যদি grid[row, col] খালি থাকে, তবে true রিটার্ন করুন, অন্যথায় false।

শুরু
  গ্রিডের প্রতিটি রো r-এর জন্য করুন
    গ্রিডের প্রতিটি কলাম c-এর জন্য করুন
      যদি grid[r, c] = 0, তবে
        return true
      শেষ
    শেষ
  false রিটার্ন করুন
শেষ

isValidPlace(row, col, num)

ইনপুট: গ্রিডের রো, কলাম, এবং চেক করার নাম্বার।

আউটপুট: True, যখন grid[row, col] পজিশনে নাম্বার রাখা বৈধ।

শুরু
  যদি isPresentInRow(row, num) এবং isPresentInCol(col, num) এবং isPresntInBox(row - row mod 3, col - col mod 3, num) সবগুলো false হয়, তবে
    return true
শেষ

solveSudoku(Sudoku Grid)

ইনপুট: অনসল্ভড সুডোকু গ্রিড।

আউটপুট: সমাধান করা গ্রিড।

শুরু
  যদি গ্রিডে কোনো খালি প্লেস নেই, তবে
    return true
  নাম্বার ১ থেকে ৯ পর্যন্ত, করুন
    যদি isValidPlace(row, col, number), তবে
      grid[row, col] := number
      যদি solveSudoku = true, তবে
        return true
      grid[row, col] := 0
  শেষ
  return false
শেষ

উদাহরণ

#include <iostream> #define N 9 using namespace std; 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} }; bool isPresentInCol(int col, int num) { //চেক করুন num কলামে আছে কিনা for (int row = 0; row < N; row++) if (grid[row][col] == num) return true; return false; } bool isPresentInRow(int row, int num) { //চেক করুন num রোতে আছে কিনা for (int col = 0; col < N; col++) if (grid[row][col] == num) return true; return false; } bool isPresentInBox(int boxStartRow, int boxStartCol, int num) { //চেক করুন num ৩x৩ বক্সে আছে কিনা 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; } void sudokuGrid() { //সল্ভ করার পর সুডোকু গ্রিড প্রিন্ট করুন for (int row = 0; row < N; row++) { for (int col = 0; col < N; col++) { if(col == 3 || col == 6) cout << " | "; cout << grid[row][col] <<" "; } if(row == 2 || row == 5) { cout << endl; for(int i = 0; i<N; i++) cout << "---"; } cout << endl; } } bool findEmptyPlace(int &row, int &col) { //খালি লোকেশন পান এবং রো ও কলাম আপডেট করুন for (row = 0; row < N; row++) for (col = 0; col < N; col++) if (grid[row][col] == 0) //০ দিয়ে মার্ক করা খালি return true; return false; } bool isValidPlace(int row, int col, int num) { //যদি আইটেম কলাম, রো এবং কারেন্ট ৩x৩ বক্সে না থাকে return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3 , col - col%3, num); } bool solveSudoku() { int row, col; if (!findEmptyPlace(row, col)) return true; //যখন সব প্লেস ফিল্ড হয়েছে for (int num = 1; num <= 9; num++) { //বৈধ নাম্বার ১ - ৯ if (isValidPlace(row, col, num)) { //ভ্যালিডেশন চেক, যদি হ্যাঁ, গ্রিডে নাম্বার রাখুন grid[row][col] = num; if (solveSudoku()) //রিকার্শিভলি গ্রিডের অন্য রুমের জন্য যান return true; grid[row][col] = 0; //যখন কন্ডিশন স্যাটিসফাই না হয়, আনসাইনড স্পেসে ফিরে যান } } return false; } int main() { if (solveSudoku() == true) sudokuGrid(); else cout << "No solution exists"; }

আউটপুট

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