Điền 8 số vào lưới với các điều kiện cho trước trong C ++

Giả sử chúng ta muốn đặt 1, 2, 3, 4, 5, 6, 7, 8, vào tám hình tròn trong hình đã cho, theo cách này để không có số nào liền kề với một số bên cạnh nó trong dãy.

Vì vậy, nếu đầu vào giống như

0	- 1	- 1	0
- 1	- 1	- 1	- 1
0	- 1	- 1	0

thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

N:=3, M:=4
NOTCONSIDERED:=-1
Xác định một hàm present_in_grid (), hàm này sẽ lấy lưới [N] [M], num,
để khởi tạo i:=0, khi i
để khởi tạo j:=0, khi j
nếu lưới [i, j] giống với num, thì -
- trả về true

trả về false

Xác định một hàm isSafe (), hàm này sẽ lấy lưới [N] [M], row, col, num,

nếu hàng giống 0 và col giống 1, thì -

if present_in_grid (grid, num) hoặc | num - grid [row, col + 1] | <=1 hoặc | num - grid [row + 1, col] | <=1 hoặc | num - grid [row + 1, col - 1] | <=1 hoặc | num - grid [row + 1, col + 1] | <=1, sau đó -
- trả về false

ngược lại khi hàng giống 0 và col bằng 2 thì -

if present_in_grid (grid, num) hoặc | num - grid [row, col - 1] | <=1 hoặc | num - grid [row + 1, col] | <=1 hoặc | num - grid [row + 1, col + 1] | <=1 hoặc | num - grid [row + 1, col - 1] | <=1, sau đó -
- trả về false

ngược lại khi hàng giống 1 và col giống 0, thì -

if present_in_grid (grid, num) hoặc | num - grid [row - 1, col + 1] | <=1 hoặc | num - grid [row, col + 1] | <=1 hoặc | num - grid [row + 1, col + 1] | <=1, sau đó -
trả về false

ngược lại khi hàng giống 1 và col giống 3 thì -

if present_in_grid (grid, num) hoặc | num - grid [row - 1, col - 1] | <=1 hoặc | num - grid [row, col - 1] | <=1 hoặc | num - grid [row + 1, col - 1] | <=1, sau đó -
- trả về false

ngược lại khi hàng giống 2 và col giống 1, thì -

if present_in_grid (grid, num) hoặc | num - grid [row - 1, col - 1] | <=1 hoặc | num - grid [row - 1, col] | <=1 hoặc | num - grid [row - 1, col + 1] | <=1 hoặc | num - grid [row, col + 1] | <=1, sau đó -
- trả về false

ngược lại khi hàng giống 2 và col giống 2 thì -

if present_in_grid (grid, num) hoặc | num - grid [row, col - 1] | <=1 hoặc | num - grid [row - 1, col] | <=1 hoặc | num - grid [row - 1, col + 1] | <=1 hoặc | num - grid [row - 1, col - 1] | <=1, sau đó -
- trả về false

ngược lại khi hàng giống 1 và col giống 1, thì -

if present_in_grid (grid, num) hoặc | num - grid [row, col - 1] | <=1 hoặc | num - grid [row - 1, col] | <=1 hoặc | num - grid [row - 1, col + 1] | <=1 hoặc | num - grid [row, col + 1] | <=1 hoặc | num - grid [row + 1, col + 1] | <=1 hoặc | num - grid [row + 1, col] | <=1, sau đó -
- trả về false

ngược lại khi hàng giống 1 và col giống 2 thì -

if present_in_grid (grid, num) hoặc | num - grid [row, col - 1] | <=1 hoặc | num - grid [row - 1, col] | <=1 hoặc | num - grid [row + 1, col - 1] | <=1 hoặc | num - grid [row, col + 1] | <=1 hoặc | num - grid [row - 1, col - 1] | <=1 hoặc | num - grid [row + 1, col] | 1, sau đó -
- trả về false

trả về true

Xác định một hàm search_free_location (), hàm này sẽ lấy lưới [N] [M], row, col,

để khởi tạo hàng:=0, khi hàng
để khởi tạo col:=0, khi col
nếu lưới [hàng, cột] giống với NOTCONSIDERED, thì -
- trả về true

trả về false

Xác định một hàm Solve (), hàm này sẽ lấy lưới [N] [M],

nếu search_free_location (lưới, hàng, cột) là sai, thì -

trả về true

để khởi tạo num:=1, khi num <=8, cập nhật (tăng num lên 1), thực hiện -

if isSafe (grid, row, col, num), then -
- lưới [hàng, col]:=num
- nếu Solve (lưới) là true, thì -
  - trả về true
grid [row, col]:=NOTCONSIDERED

trả về false

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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";
}

Đầu vào

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

Đầu ra

  3 5
7 1 8 2
  4 6