วางตัวเลข 1-8 ในกริด 3x4 โดยไม่ให้ตัวเลขติดกันติดลำดับใน C++

โจทย์

ต้องการวางตัวเลข 1, 2, 3, 4, 5, 6, 7, 8 ลงในวงกลม 8 วงในกริด 3x4 (บางช่องเป็นช่องว่าง) โดยที่ไม่มีตัวเลขใดอยู่ติดกับตัวเลขที่ติดลำดับกัน (เช่น 1 ไม่ติด 2, 2 ไม่ติด 3, ฯลฯ)

ขั้นตอนการแก้ปัญหา

• กำหนด N=3, M=4, NOTCONSIDERED=-1
• ฟังก์ชัน present_in_grid(): ตรวจสอบว่าตัวเลขถูกใช้ไปแล้วหรือยัง
• ฟังก์ชัน isSafe(): ตรวจสอบว่าการวางตัวเลขที่ตำแหน่ง (row, col) ปลอดภัยหรือไม่ โดยพิจารณาจากเพื่อนบนซ้าย ขวา บน ล่าง และมุม ตามตำแหน่งที่กำหนดในกริด
• ฟังก์ชัน search_free_location(): หาช่องว่างถัดไป
• ฟังก์ชัน Solve(): ใช้ Backtracking ลองวางตัวเลข 1-8 ในช่องว่าง ถ้าผ่าน isSafe ให้วางและเรียก Solve ซ้ำ ถ้าไม่สำเร็จให้ย้อนกลับ (backtrack)

ตัวอย่างโค้ด 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) { ... }
bool isSafe(int grid[N][M], int row, int col, int num) { ... }
bool search_free_location(int grid[N][M], int& row, int& col) { ... }
void show_res(int grid[N][M]) { ... }
bool Solve(int grid[N][M]) { ... }

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