समस्या विवरण
हम 1, 2, 3, 4, 5, 6, 7, 8 को दिए गए चित्र में आठ वृत्तों में इस तरह रखना चाहते हैं कि कोई भी संख्या उस संख्या से सटी न हो जो अनुक्रम में उसके बगल में है।
इनपुट ग्रिड
| 0 | -1 | -1 | 0 |
| -1 | -1 | -1 | -1 |
| 0 | -1 | -1 | 0 |
आउटपुट

एल्गोरिदम चरण
- N := 3, M := 4
- NOTCONSIDERED := -1
- फ़ंक्शन present_in_grid(grid, num) परिभाषित करें जो जांचता है कि संख्या पहले से ग्रिड में है या नहीं।
- फ़ंक्शन isSafe(grid, row, col, num) परिभाषित करें जो जांचता है कि दी गई स्थिति पर संख्या रखना सुरक्षित है या नहीं (आसन्न कोशिकाओं में लगातार संख्याएं नहीं होनी चाहिए)।
- फ़ंक्शन search_free_location(grid, row, col) परिभाषित करें जो अगली खाली कोशिका ढूंढता है।
- बैट्रैकिंग का उपयोग करके फ़ंक्शन Solve(grid) परिभाषित करें जो ग्रिड को भरता है।
C++ कार्यान्वयन
#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) {
// प्रत्येक कोशिका स्थिति के लिए विस्तृत आसन्नता जांच
// ... (कोड में पूर्ण कार्यान्वयन देखें)
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