C++ এ প্রদত্ত শর্ত সহ গ্রিডে 8টি সংখ্যা পূরণ করুন

ধরুন আমরা প্রদত্ত চিত্রের আটটি বৃত্তের মধ্যে 1, 2, 3, 4, 5, 6, 7, 8 রাখতে চাই, এভাবে যে ক্রমানুসারে এর পাশে থাকা একটি সংখ্যার সংলগ্ন কোনো সংখ্যা নেই।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• N :=3, M :=4
• বিবেচিত নয় :=-1
• একটি ফাংশন সংজ্ঞায়িত করুন present_in_grid(), এটি গ্রিড নেবে[N][M], সংখ্যা,
• আরম্ভ করার জন্য i :=0, যখন i
• আরম্ভ করার জন্য j :=0, যখন j করুন
• যদি গ্রিড[i, j] সংখ্যার সমান হয়, তাহলে −
  • সত্যে ফিরে আসুন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <cmath>
#include <iostream>
#define N 3
#define M 4
#define NOTCONSIDERED -1
using namespace std;
bool present_in_grid(int grid[N][M], int num) {
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++)
         if (grid[i][j] == num)
            return true;
   }
   return false;
}
bool isSafe(int grid[N][M], int row, int col, int num) {
   if (row == 0 && col == 1) {
      if (present_in_grid(grid, num) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1))
         return false;
   }
   else if (row == 0 && col == 2) {
      if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1))
         return false;
   }
   else if (row == 1 && col == 0) {
      if (present_in_grid(grid, num) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1))
         return false;
   }
   else if (row == 1 && col == 3) {
      if (present_in_grid(grid, num) || (abs(num - grid[row - 1][col - 1]) <= 1) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1))
         return false;
   }
   else if (row == 2 && col == 1) {
   if (present_in_grid(grid, num) || (abs(num - grid[row - 1][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1))
      return false;
   }
   else if (row == 2 && col == 2) {
      if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row - 1][col - 1]) <= 1))
         return false;
   }
   else if (row == 1 && col == 1) {
      if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row - 1][col + 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row + 1][col + 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1))
         return false;
   }
   else if (row == 1 && col == 2) {
      if (present_in_grid(grid, num) || (abs(num - grid[row][col - 1]) <= 1) || (abs(num - grid[row - 1][col]) <= 1) || (abs(num - grid[row + 1][col - 1]) <= 1) || (abs(num - grid[row][col + 1]) <= 1) || (abs(num - grid[row - 1][col - 1]) <= 1) || (abs(num - grid[row + 1][col]) <= 1))
         return false;
   }
   return true;
}
bool search_free_location(int grid[N][M], int& row, int& col) {
   for (row = 0; row < N; row++)
   for (col = 0; col < M; col++) {
      if (grid[row][col] == NOTCONSIDERED)
         return true;
   }
   return false;
}
void show_res(int grid[N][M]) {
   for (int i = 0; i < N; i++) {
      if (i == 0 || i == N - 1)
         cout << " ";
      for (int j = 0; j < M; j++) {
         if (grid[i][j] == 0)
            cout << " ";
         else
            cout << grid[i][j] << " ";
      }
      cout << endl;
   }
}
bool Solve(int grid[N][M]) {
   int row, col;
   if (!search_free_location(grid, row, col))
   return true;
   for (int num = 1; num <= 8; num++) {
      if (isSafe(grid, row, col, num)) {
         grid[row][col] = num;
         if (Solve(grid))
            return true;
         grid[row][col] = NOTCONSIDERED;
      }
   }
   return false;
}
int main(){
   int grid[N][M] = { { 0, -1, -1, 0 },
      { -1, -1, -1, -1 },
      { 0, -1, -1, 0 } };
   if (Solve(grid))
      show_res(grid);
   else
      cout << "Not possible";
}

ইনপুট

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

আউটপুট

  3 5
7 1 8 2
  4 6