21.3 backtracking

วิธีในหน้า 21.2 สร้างคำตอบให้ครบทุกช่องก่อน แล้วค่อยตรวจว่าใช้ได้ไหม ถ้าคำตอบส่วนใหญ่ผิดกฎตั้งแต่ช่องแรกๆ ก็เสียเวลาสร้างส่วนที่เหลือไปเปล่าๆ backtracking (การย้อนรอย) สร้างคำตอบทีละช่อง และเลือกเฉพาะตัวเลือกที่ยังไม่ผิดกฎ ถ้าถึงช่องไหนแล้วไม่มีตัวเลือกเหลือ ก็ถอยกลับไปเปลี่ยนตัวเลือกของช่องก่อนหน้า โครง เลือก ลอง คืนสภาพ ในหน้า 9.5 คือ backtracking อยู่แล้ว หน้านี้เอาไปใช้กับโจทย์ที่มีกฎจริงๆ คือ N-Queens ผลรวมเซตย่อย และซูโดกุ

ต้นไม้การค้นหา

โจทย์ N-Queens คือวางควีน N ตัวบนกระดาน N × N ไม่ให้มีสองตัวไหนกินกันได้ ควีนกินกันได้เมื่ออยู่แถวเดียวกัน คอลัมน์เดียวกัน หรือแนวทแยงเดียวกัน แต่ละแถวจึงมีควีนได้ตัวเดียวพอดี คำตอบหนึ่งแบบคือคอลัมน์ของควีนในแถวที่ 1 ถึง N

backtracking วางทีละแถว แถวละหนึ่งตัว ทุกครั้งที่วางให้เลือกเฉพาะคอลัมน์ที่ไม่โดนควีนแถวก่อนๆ กิน ภาพนี้คือการค้นหาทั้งหมดเมื่อ N = 4 แต่ละกล่องคือสถานะระหว่างทาง ตัวเลขในกล่องคือคอลัมน์ของควีนในแถวที่วางไปแล้วเรียงตามแถว เช่น 14 คือแถว 1 วางคอลัมน์ 1 แถว 2 วางคอลัมน์ 4 เส้นจากกล่องลงไปคือตัวเลือกที่ยังไม่ผิดกฎ ภาพแบบนี้เรียกว่า ต้นไม้การค้นหา (search tree) แต่ละกล่องในต้นไม้เรียกว่าโหนด (node) แบบเดียวกับต้นไม้ของ set ในหน้า 20.1

กล่องเส้นประคือทางตัน เช่น 13 วางแถว 3 ที่ไหนก็โดนกิน จึงไม่มีเส้นลงไป ต้องถอยกลับไปลอง 14 แทน กล่องสีคือคำตอบที่วางครบ 4 ตัว มีสองแบบ คือ 2413 กับ 3142 ทั้งต้นไม้มี 17 กล่อง เทียบกับการสร้างทุกการเรียงสับเปลี่ยนของคอลัมน์ก่อนแล้วค่อยตรวจ ซึ่งต้องสร้างกระดานเต็ม 4! = 24 กระดาน กิ่งที่ตันตั้งแต่แถวที่ 2 ไม่ถูกสร้างต่อเลย ยิ่ง N ใหญ่ ส่วนที่ไม่ต้องสร้างยิ่งมาก

N-Queens

ก่อนวางควีนที่แถว row คอลัมน์ c ต้องรู้ให้เร็วว่าโดนกินไหม ไม่ต้องไล่ดูควีนทุกตัว ใช้อาเรย์จำไว้สามอัน

col_used[c] คอลัมน์ c มีควีนแล้ว
diag1_used[row + c] แนวทแยงที่ขึ้นไปทางขวา ทุกช่องบนเส้นเดียวกันมี row + c เท่ากัน มีค่า 0 ถึง 2N - 2
diag2_used[row - c + N - 1] แนวทแยงที่ลงไปทางขวา ทุกช่องบนเส้นเดียวกันมี row - c เท่ากัน บวก N - 1 ให้ไม่ติดลบ ใช้เป็นตำแหน่งในอาเรย์ได้

#include <bits/stdc++.h>
using namespace std;

int n;
int queen_col[15];
bool col_used[15], diag1_used[30], diag2_used[30];
long long solutions = 0, nodes = 0;

void print_board()
{
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            cout << (queen_col[r] == c ? 'Q' : '.');
        }
        cout << '\n';
    }
}

void place(int row)
{
    nodes++; // (1)!
    if (row == n) {
        if (solutions == 0) {
            print_board();
        }
        solutions++;
        return;
    }
    for (int c = 0; c < n; c++) {
        int d1 = row + c, d2 = row - c + n - 1;
        if (col_used[c] || diag1_used[d1] || diag2_used[d2]) { // (2)!
            continue;
        }
        queen_col[row] = c;
        col_used[c] = diag1_used[d1] = diag2_used[d2] = true; // (3)!
        place(row + 1);
        col_used[c] = diag1_used[d1] = diag2_used[d2] = false; // (4)!
    }
}

int main()
{
    cin >> n;
    place(0);
    cout << "solutions " << solutions << '\n';
    cout << "nodes " << nodes << '\n';
    return 0;
}

นับว่าเรียก place กี่ครั้ง ซึ่งก็คือจำนวนโหนดในต้นไม้การค้นหา ใช้วัดว่าค้นหาหนักแค่ไหน ไม่เกี่ยวกับคำตอบ
ตัดตัวเลือกที่ผิดกฎทิ้งตั้งแต่ตอนนี้ ไม่ปล่อยให้ลงไปสร้างแถวที่เหลือ บรรทัดนี้คือส่วนที่ทำให้ backtracking ต่างจากลองทุกแบบ
เลือก วางควีนแล้วจดว่าคอลัมน์และแนวทแยงทั้งสองเส้นถูกใช้แล้ว = ที่ต่อกันหลายตัวทำจากขวาไปซ้าย และแต่ละ = ส่งค่าที่ใส่ต่อไปให้ตัวทางซ้าย บรรทัดนี้จึงเท่ากับเขียน diag2_used[d2] = true; diag1_used[d1] = true; col_used[c] = true; สามบรรทัด บรรทัดคืนสภาพก็เช่นกัน
คืนสภาพ หลังลองทุกแบบที่มีควีนตัวนี้แล้ว ปลดออก ให้รอบถัดไปของลูปลองคอลัมน์อื่น ถ้าลืม แถวก่อนหน้าจะเห็นช่องว่างเป็นช่องที่โดนกินทั้งที่ไม่มีควีนแล้ว

.Q..
...Q
Q...
..Q.
solutions 2
nodes 17

กระดานที่พิมพ์คือคำตอบ 2413 ในภาพ และ nodes เท่ากับ 17 โหนดในภาพพอดี ป้อน 8 ได้ solutions 92 กับ nodes 2057 ตารางนี้เทียบกับการลองทุกการเรียงสับเปลี่ยนของคอลัมน์ด้วย next_permutation แล้วตรวจแนวทแยงทุกคู่ทีหลัง วัดบนเครื่องเดียวกับหน้า 21.1 แบบ -O2 ค่ากลางของ 3 ถึง 5 ครั้ง

N	คำตอบ	จำนวนโหนดของ backtracking	N! กระดานที่ต้องตรวจ	ลองทุกลำดับ	backtracking
8	92	2,057	40,320	0.024 วินาที	0.020 วินาที
10	724	35,539	3,628,800	0.051 วินาที	0.025 วินาที
11	2,680	166,926	39,916,800	0.276 วินาที	0.025 วินาที
12	14,200	856,189	479,001,600	3.143 วินาที	0.054 วินาที
13	73,712	4,674,890	6.2 × 10⁹	ไม่ได้รัน	0.223 วินาที
14	365,596	27,358,553	8.7 × 10¹⁰	ไม่ได้รัน	1.176 วินาที

ที่ N = 12 backtracking ไปแค่ 8.6 × 10⁵ โหนด ขณะที่ลองทุกลำดับต้องตรวจเกือบ 5 × 10⁸ กระดาน แบบ Code::Blocks ต่างกันยิ่งกว่า คือ 49.4 วินาทีกับ 0.067 วินาที แต่ backtracking ก็ยังเป็นเวลาแบบเลขชี้กำลังอยู่ดี N เพิ่มหนึ่ง จำนวนโหนดเพิ่มราว 5 เท่า N = 14 ก็เกินหนึ่งวินาทีแล้ว ตัดกิ่งได้ดีแค่ไหนต้องวัดเอา ไม่มีสูตรตายตัวแบบ Big O ในบทที่ 18

โครงของ backtracking

โจทย์ backtracking ทุกข้อเขียนตามโครงเดียวกัน เปลี่ยนแค่ว่าสถานะคืออะไร ตัวเลือกคืออะไร และกฎคืออะไร

go(สถานะตอนนี้)
    ถ้าสร้างครบแล้ว  บันทึกหรือนับคำตอบ แล้วกลับ
    สำหรับทุกตัวเลือก x ของช่องถัดไป
        ถ้า x ผิดกฎ  ข้าม
        เลือก x  (เปลี่ยนสถานะ)
        go(สถานะใหม่)
        คืนสภาพ x  (เปลี่ยนสถานะกลับเหมือนก่อนเลือก)

คำถามที่ต้องตอบก่อนเขียน คือแต่ละชั้นของ recursion เติมช่องไหน (N-Queens เติมทีละแถว) ตัวเลือกมีอะไรบ้าง (คอลัมน์ 0 ถึง N - 1) และเช็กกฎยังไงให้เร็ว (อาเรย์สามอัน)

ผลรวมเซตย่อย

ห้องเรียนมีงบซื้อของขวัญวันครู S บาทพอดี ร้านมีของ n ชิ้นราคาต่างๆ ให้พิมพ์ทุกชุดของของที่ราคารวมเท่ากับ S พอดี โจทย์แบบนี้เรียกว่า ผลรวมเซตย่อย (subset sum) ใช้ bitmask ในหน้า 21.2 ก็ได้ แต่เขียนแบบ backtracking ไล่ทีละชิ้น ชั้นที่ i ตัดสินใจเรื่องชิ้นที่ i ว่าจะเลือกหรือไม่ และเก็บชิ้นที่เลือกไว้ใน vector

#include <bits/stdc++.h>
using namespace std;

int n, target;
vector<int> price;
vector<int> chosen;

void go(int i, int sum)
{
    if (i == n) {
        if (sum == target) {
            for (int k = 0; k < (int)chosen.size(); k++) {
                cout << chosen[k] << (k + 1 < (int)chosen.size() ? ' ' : '\n');
            }
        }
        return;
    }
    chosen.push_back(price[i]); // (1)!
    go(i + 1, sum + price[i]);
    chosen.pop_back(); // (2)!
    go(i + 1, sum); // (3)!
}

int main()
{
    cin >> n >> target;
    price.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }
    go(0, 0);
    return 0;
}

เลือก ชิ้นที่ i ใส่ท้าย vector แล้วลองทุกแบบของชิ้นที่เหลือ ผลรวมส่งไปเป็นพารามิเตอร์ จึงไม่ต้องคืนสภาพเอง เพราะ sum ของชั้นนี้ไม่ได้เปลี่ยน
คืนสภาพ เอาชิ้นที่ i ออกจาก vector ก่อนลองทางที่ไม่เลือก vector เป็นของที่ทุกชั้นใช้ร่วมกัน ต่างจาก sum
ทางที่สอง ไม่เลือกชิ้นที่ i ทุกชั้นแตกเป็นสองทางแบบสตริงฐานสองในหน้า 9.5 รวม 2ⁿ ชุดที่ไปถึงชั้นล่างสุด

6 50
20 15 30 10 5 25

โปรแกรมนี้ยังไม่ได้ตัดอะไรเลย ไปถึงชั้นล่างครบ 2ⁿ ชุดแล้วค่อยตรวจผลรวม ทั้งที่ระหว่างทางรู้ได้ตั้งแต่เนิ่นๆ เช่น เลือก 20 15 30 ไปแล้วได้ 65 เกิน 50 แล้ว ชิ้นที่เหลือราคาเป็นบวกทั้งนั้น เติมอีกเท่าไรก็ไม่มีทางกลับมาเป็น 50 การตัดกิ่งแบบนี้คือเรื่องของหน้า 21.4

ซูโดกุ 4 × 4

ซูโดกุขนาดเล็ก ตาราง 4 × 4 แบ่งเป็นกล่อง 2 × 2 สี่กล่อง ต้องเติมเลข 1 ถึง 4 ให้ทุกแถว ทุกคอลัมน์ และทุกกล่องมีเลขครบไม่ซ้ำ ช่องที่เป็น 0 คือช่องว่าง เติมทีละช่องจากซ้ายไปขวา บนลงล่าง ให้ช่องที่ pos คือแถว pos / 4 คอลัมน์ pos % 4 เหมือนเปลี่ยนตารางเป็นแถวยาวแถวเดียว

#include <bits/stdc++.h>
using namespace std;

int grid[4][4];

bool can_put(int r, int c, int d)
{
    for (int k = 0; k < 4; k++) {
        if (grid[r][k] == d || grid[k][c] == d) {
            return false;
        }
    }
    int top = r / 2 * 2, left = c / 2 * 2; // (1)!
    for (int i = top; i < top + 2; i++) {
        for (int j = left; j < left + 2; j++) {
            if (grid[i][j] == d) {
                return false;
            }
        }
    }
    return true;
}

bool solve(int pos)
{
    if (pos == 16) {
        return true;
    }
    int r = pos / 4, c = pos % 4;
    if (grid[r][c] != 0) {
        return solve(pos + 1); // (2)!
    }
    for (int d = 1; d <= 4; d++) {
        if (can_put(r, c, d)) {
            grid[r][c] = d;
            if (solve(pos + 1)) { // (3)!
                return true;
            }
            grid[r][c] = 0;
        }
    }
    return false;
}

int main()
{
    for (int r = 0; r < 4; r++) {
        for (int c = 0; c < 4; c++) {
            cin >> grid[r][c];
        }
    }
    if (!solve(0)) {
        cout << "no solution\n";
        return 0;
    }
    for (int r = 0; r < 4; r++) {
        for (int c = 0; c < 4; c++) {
            cout << grid[r][c] << (c < 3 ? ' ' : '\n');
        }
    }
    return 0;
}

มุมซ้ายบนของกล่องที่ช่อง (r, c) อยู่ หารแล้วคูณ 2 ปัดลงไปหาเลขคู่ที่ใกล้ที่สุด เช่น r = 3 ได้ 2
ช่องที่มีเลขให้มาแล้วไม่ต้องเลือก ข้ามไปช่องถัดไปเลย
solve คืน true เมื่อเติมครบ พอเจอคำตอบแรกแล้วทุกชั้นคืน true ต่อกันขึ้นไปทันที ไม่ลองตัวเลือกที่เหลือ ตารางจึงค้างค่าของคำตอบไว้ให้พิมพ์ ถ้าโจทย์ต้องการนับทุกคำตอบ ให้ใช้แบบ N-Queens ที่ไม่หยุด

โปรแกรมนี้ตรวจกฎเฉพาะเลขที่ตัวเองเติม ไม่ได้ตรวจว่าเลขที่ให้มาตั้งแต่ต้นขัดกันเองหรือเปล่า ถ้าโจทย์ไม่ได้รับประกันเรื่องนี้ ต้องตรวจเพิ่มก่อนเริ่มค้น ซูโดกุ 9 × 9 ใช้โครงเดียวกันได้ แต่ปริศนายากๆ บางข้อจะช้า ต้องเลือกเติมช่องที่มีตัวเลือกน้อยที่สุดก่อน ซึ่งเป็นการตัดกิ่งอีกแบบหนึ่ง

ลองทำให้พัง

แบบที่ 1 ลืม pop_back

ในโปรแกรม subset-sum ลบบรรทัด chosen.pop_back(); ออก คอมไพล์ผ่านโดยไม่มีคำเตือน ป้อนข้อมูลชุดเดิมได้

20 15 30 10 5 25 25 5 25 25 10 5 25
20 15 30 10 5 25 25 5 25 25 10 5 25 25 5 25 25 30 10 5 25 25 5 25 25
20 15 30 10 5 25 25 5 25 25 10 5 25 25 5 25 25 30 10 5 25 25 5 25 25 10 5 25 25 5 25
20 15 30 10 5 25 25 5 25 25 10 5 25 25 5 25 25 30 10 5 25 25 5 25 25 10 5 25 25 5 25 25 15 30 10 5 25 25 5 25
20 15 30 10 5 25 25 5 25 25 10 5 25 25 5 25 25 30 10 5 25 25 5 25 25 10 5 25 25 5 25 25 15 30 10 5 25 25 5 25 25 10 5 25 25

ยังพิมพ์ห้าบรรทัดเท่าเดิม เพราะ sum ยังถูกต้อง แต่ของในแต่ละบรรทัดยาวขึ้นเรื่อยๆ ทุกชิ้นที่เคยเลือกค้างอยู่ใน vector ไม่เคยถูกเอาออก ของที่เป็นพารามิเตอร์อย่าง sum คืนสภาพเองตอนฟังก์ชันจบ แต่ของที่ทุกชั้นใช้ร่วมกันอย่าง vector global หรืออาเรย์ col_used ต้องคืนสภาพเองทุกครั้ง

แบบที่ 2 ลืมลบเลขที่เติมผิด

ในโปรแกรม sudoku ลบบรรทัด grid[r][c] = 0; ที่อยู่หลัง if (solve(pos + 1)) ออก คอมไพล์ผ่านโดยไม่มีคำเตือน ป้อนตารางเดิมได้

no solution

ปริศนาที่มีคำตอบกลายเป็นไม่มีคำตอบ เพราะเลขที่ลองแล้วไปต่อไม่ได้ยังค้างอยู่ในตาราง พอถอยกลับไปเปลี่ยนช่องก่อนหน้า ช่องนี้ไม่เป็น 0 แล้ว บรรทัด if (grid[r][c] != 0) จึงนึกว่าเป็นเลขที่โจทย์ให้มา ข้ามไปไม่ลองใหม่ เลขผิดนั้นยังไปบังตัวเลือกของช่องอื่นด้วย

สรุป

backtracking สร้างคำตอบทีละช่อง ตัดตัวเลือกที่ผิดกฎทิ้งทันที ถ้าไม่มีตัวเลือกเหลือก็ถอยกลับไปเปลี่ยนช่องก่อนหน้า
ต้นไม้การค้นหามีกล่องคือสถานะระหว่างทาง นับจำนวนกล่องด้วยตัวแปร nodes เพื่อดูว่าค้นหาหนักแค่ไหน
N-Queens วางทีละแถว ใช้อาเรย์จำคอลัมน์ row + c และ row - c + N - 1 ตรวจได้ใน O(1)
ทุกอย่างที่ทุกชั้นใช้ร่วมกัน ทั้ง vector อาเรย์ และตาราง ต้องคืนสภาพหลังลองเสร็จ
ต้องการแค่คำตอบเดียว ให้ฟังก์ชันคืน bool แล้วหยุดทันทีที่เจอ ต้องการนับทุกคำตอบ ให้ไล่จนครบ