C++에서 주어진 조건으로 그리드에 8개의 숫자 채우기

주어진 그림에서 8개의 원에 1, 2, 3, 4, 5, 6, 7, 8을 배치하려고 한다고 가정해 보겠습니다. 이렇게 하면 시퀀스에서 옆에 있는 숫자와 인접한 숫자가 없습니다.

따라서 입력이 다음과 같으면

그러면 출력은

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• N :=3, M :=4
• 고려하지 않음 :=-1
• present_in_grid() 함수를 정의하면 grid[N][M], num,
• 초기화 i의 경우:=0, i
• j 초기화의 경우:=0, j
• 그리드[i, j]가 num과 같으면 -
  • 참을 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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