สมมติว่าเราต้องการใส่ 1, 2, 3, 4, 5, 6, 7, 8 ลงในวงกลมแปดวงในรูปที่กำหนด ด้วยวิธีนี้ไม่มีตัวเลขใดอยู่ติดกับตัวเลขที่อยู่ติดกันในลำดับ
ดังนั้นหากอินพุตเป็นแบบ
| 0 | - 1 | - 1 | 0 |
| - 1 | - 1 | - 1 | - 1 |
| 0 | - 1 | - 1 | 0 |
แล้วผลลัพธ์ที่ได้จะเป็น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- N :=3, M :=4
- ไม่พิจารณา :=-1
- กำหนดฟังก์ชัน present_in_grid() จะใช้ grid[N][M], num,
- สำหรับการเริ่มต้น i :=0 เมื่อ i
- สำหรับการเริ่มต้น j :=0 เมื่อ j
- ถ้า grid[i, j] เหมือนกับ num แล้ว −
- คืนค่าจริง
- สำหรับการเริ่มต้น j :=0 เมื่อ j
- ถ้า present_in_grid(grid, num) หรือ |num - grid[row, col + 1]| <=1 หรือ |num - grid[row + 1, col]| <=1 หรือ |num - grid[row + 1, col - 1]| <=1 หรือ |num - grid[row + 1, col + 1]| <=1 จากนั้น −
- คืนค่าเท็จ
- ถ้า present_in_grid(grid, num) หรือ |num - grid[row, col - 1]| <=1 หรือ |num - grid[row + 1, col]| <=1 หรือ |num - grid[row + 1, col + 1]| <=1 หรือ |num - grid[row + 1, col - 1]| <=1 จากนั้น −
- คืนค่าเท็จ
- if present_in_grid(grid, num) หรือ |num - grid[row - 1, col + 1]| <=1 หรือ |num - grid[row, col + 1]| <=1 หรือ |num - grid[row + 1, col + 1]| <=1 จากนั้น −
- คืนค่าเท็จ
- ถ้า present_in_grid(grid, num) หรือ |num - grid[row - 1, col - 1]| <=1 หรือ |num - grid[row, col - 1]| <=1 หรือ |num - grid[row + 1, col - 1]| <=1 จากนั้น −
- คืนค่าเท็จ
- ถ้า present_in_grid(grid, num) หรือ |num - grid[row - 1, col - 1]| <=1 หรือ |num - grid[row - 1, col]| <=1 หรือ |num - grid[row - 1, col + 1]| <=1 หรือ |num - grid[row, col + 1]| <=1 จากนั้น −
- คืนค่าเท็จ
- ถ้า present_in_grid(grid, num) หรือ |num - grid[row, col - 1]| <=1 หรือ |num - grid[row - 1, col]| <=1 หรือ |num - grid[row - 1, col + 1]| <=1 หรือ |num - grid[row - 1, col - 1]| <=1 จากนั้น −
- คืนค่าเท็จ
- ถ้า present_in_grid(grid, num) หรือ |num - grid[row, col - 1]| <=1 หรือ |num - grid[row - 1, col]| <=1 หรือ |num - grid[row - 1, col + 1]| <=1 หรือ |num - grid[row, col + 1]| <=1 หรือ |num - grid[row + 1, col + 1]| <=1 หรือ |num - grid[row + 1, col]| <=1 จากนั้น −
- คืนค่าเท็จ
- ถ้า present_in_grid(grid, num) หรือ |num - grid[row, col - 1]| <=1 หรือ |num - grid[row - 1, col]| <=1 หรือ |num - grid[row + 1, col - 1]| <=1 หรือ |num - grid[row, col + 1]| <=1 หรือ |num - grid[row - 1, col - 1]| <=1 หรือ |num - grid[row + 1, col]| 1 จากนั้น −
- คืนค่าเท็จ
- สำหรับการเริ่มต้นแถว :=0 เมื่อแถว
- สำหรับการเริ่มต้น col :=0 เมื่อ col
- ถ้า grid[row, col] เหมือนกับ NOTCONSIDERED แล้ว −
- คืนค่าจริง
- สำหรับการเริ่มต้น col :=0 เมื่อ col
- คืนค่าจริง
- if isSafe(grid, row, col, num) แล้ว −
- grid[row, col] :=num
- ถ้า Solve(grid) เป็นจริง −
- คืนค่าจริง
- grid[row, col] :=ไม่ได้รับการพิจารณา
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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
