Quay lui

void quay_lui(TrangThai *tt)
{
    if (da_xong(tt)) { ghi_nhan(tt); return; }

    for (moi lua chon hop le) {
        if (!an_toan(tt, lua_chon)) continue;   /* CAT TIA */

        chon(tt, lua_chon);                     /* 1. CHON */
        quay_lui(tt);                           /* 2. DE QUY */
        bo_chon(tt, lua_chon);                  /* 3. BO CHON */
    }
}

#include <stdio.h>
#include <stdlib.h>

/* q[i] = cột của quân hậu ở hàng i.
   Biểu diễn này TỰ ĐỘNG bảo đảm mỗi hàng đúng một quân,
   nên chỉ cần kiểm cột và hai đường chéo. */
static int an_toan(const int *q, int hang, int cot)
{
    for (int i = 0; i < hang; ++i) {
        if (q[i] == cot) return 0;                     /* cùng cột */

        if (abs(q[i] - cot) == hang - i) return 0;     /* cùng đường chéo */
    }

    return 1;
}

/* Đếm số lời giải với các hàng từ 0 tới hang-1 đã đặt xong. */
int n_hau(int *q, int hang, int n)
{
    if (hang == n) return 1;      /* đặt đủ n quân, một lời giải */

    int dem = 0;

    for (int cot = 0; cot < n; ++cot)
        if (an_toan(q, hang, cot)) {
            q[hang] = cot;                 /* CHỌN */
            dem    += n_hau(q, hang + 1, n);/* ĐỆ QUY */
            /* q[hang] bị ghi đè ở vòng sau, không cần bỏ chọn */
        }

    return dem;
}

int main(void)
{
    int q[16];

    printf("%3s %12s\n", "n", "so loi giai");

    for (int n = 1; n <= 12; ++n)
        printf("%3d %12d\n", n, n_hau(q, 0, n));

    return 0;
}

static void in_ban_co(const int *q, int n)
{
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            printf("%c ", (q[i] == j) ? 'Q' : '.');

        printf("\n");
    }

    printf("\n");
}

/* Tìm lời giải ĐẦU TIÊN rồi dừng, thay vì đếm hết. */
int n_hau_mot(int *q, int hang, int n)
{
    if (hang == n) return 1;

    for (int cot = 0; cot < n; ++cot)
        if (an_toan(q, hang, cot)) {
            q[hang] = cot;

            if (n_hau_mot(q, hang + 1, n)) return 1;   /* dừng ngay */
        }

    return 0;
}

/* Thay vong lap an_toan O(n) bang ba bit mask, kiem trong O(1).

   cot   : bit j bat neu cot j da bi chiem
   cheo1 : duong cheo chinh, chi so hang - cot + n - 1
   cheo2 : duong cheo phu,   chi so hang + cot                 */
static int dem_hau(int n, unsigned cot, unsigned cheo1, unsigned cheo2,
                   int hang)
{
    if (hang == n) return 1;

    int dem = 0;

    for (int c = 0; c < n; ++c) {
        unsigned bc  = 1u << c;
        unsigned b1  = 1u << (hang - c + n - 1);
        unsigned b2  = 1u << (hang + c);

        if ((cot & bc) || (cheo1 & b1) || (cheo2 & b2)) continue;

        dem += dem_hau(n, cot | bc, cheo1 | b1, cheo2 | b2, hang + 1);
    }

    return dem;
}

int n_hau_bit(int n) { return dem_hau(n, 0, 0, 0, 0); }

/* Ba lo 0/1 bang nhanh can. Voi n nho, no nhanh hon quy hoach dong
   khi W rat lon, vi no khong can bang O(n * W). */
static int tot_nhat;

/* Can tren: gia tri hien tai cong voi ba lo PHAN SO cua phan con lai.
   Ba lo phan so luon >= ba lo 0/1, nen day la can tren hop le. */
static double can_tren(const Mon *a, int n, int i, int con_lai, int gia_tri)
{
    double can = gia_tri;

    for (int k = i; k < n && con_lai > 0; ++k) {
        if (a[k].w <= con_lai) {
            can      += a[k].v;
            con_lai  -= a[k].w;
        } else {
            can += (double)a[k].v * con_lai / a[k].w;   /* cat mon */

            break;
        }
    }

    return can;
}

static void duyet(const Mon *a, int n, int i, int con_lai, int gia_tri)
{
    if (gia_tri > tot_nhat) tot_nhat = gia_tri;

    if (i == n) return;

    /* CAT TIA: nhanh nay khong the tot hon ket qua da co */
    if (can_tren(a, n, i, con_lai, gia_tri) <= tot_nhat) return;

    if (a[i].w <= con_lai)                                /* lay mon i */
        duyet(a, n, i + 1, con_lai - a[i].w, gia_tri + a[i].v);

    duyet(a, n, i + 1, con_lai, gia_tri);                 /* khong lay */
}

#include <stdio.h>
#include <string.h>

/* bang[9][9], 0 nghĩa là ô trống. */
static int an_toan(const int bang[9][9], int r, int c, int v)
{
    for (int k = 0; k < 9; ++k) {
        if (bang[r][k] == v) return 0;      /* cùng hàng */
        if (bang[k][c] == v) return 0;      /* cùng cột */
    }

    int r0 = (r / 3) * 3, c0 = (c / 3) * 3;

    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            if (bang[r0 + i][c0 + j] == v) return 0;    /* cùng khối 3x3 */

    return 1;
}

/* Tìm ô trống có ÍT lựa chọn hợp lệ nhất. Đây là cắt tỉa mạnh nhất
   của bài này, gọi là heuristic giá trị còn lại nhỏ nhất. */
static int tim_o_kho_nhat(const int bang[9][9], int *ra_r, int *ra_c)
{
    int it_nhat = 10;

    for (int r = 0; r < 9; ++r)
        for (int c = 0; c < 9; ++c) {
            if (bang[r][c] != 0) continue;

            int dem = 0;

            for (int v = 1; v <= 9; ++v)
                if (an_toan(bang, r, c, v)) ++dem;

            if (dem == 0) return -1;      /* ô này không điền được gì, quay lui ngay */

            if (dem < it_nhat) {
                it_nhat = dem;
                *ra_r   = r;
                *ra_c   = c;
            }
        }

    return (it_nhat == 10) ? 0 : 1;      /* 0 nghĩa là đã điền hết */
}

int giai(int bang[9][9])
{
    int r, c;
    int tt = tim_o_kho_nhat(bang, &r, &c);

    if (tt == 0)  return 1;      /* xong */
    if (tt == -1) return 0;      /* bế tắc */

    for (int v = 1; v <= 9; ++v)
        if (an_toan(bang, r, c, v)) {
            bang[r][c] = v;              /* CHỌN */

            if (giai(bang)) return 1;    /* ĐỆ QUY */

            bang[r][c] = 0;              /* BỎ CHỌN */
        }

    return 0;
}

#include <stdio.h>

/* Sinh moi hoan vi cua a[0..n). Doi cho tai cho, khong can bo dem phu. */
static void hoan_vi(int *a, int k, int n)
{
    if (k == n) {
        for (int i = 0; i < n; ++i) printf("%d ", a[i]);

        printf("\n");

        return;
    }

    for (int i = k; i < n; ++i) {
        int t = a[k]; a[k] = a[i]; a[i] = t;      /* CHON */

        hoan_vi(a, k + 1, n);

        t = a[k]; a[k] = a[i]; a[i] = t;          /* BO CHON */
    }
}

/* Sinh moi to hop k phan tu tu n phan tu. */
static void to_hop(int *chon, int bat_dau, int da_chon, int k, int n)
{
    if (da_chon == k) {
        for (int i = 0; i < k; ++i) printf("%d ", chon[i]);

        printf("\n");

        return;
    }

    /* CAT TIA: neu so phan tu con lai khong du thi bo nhanh */
    for (int i = bat_dau; i <= n - (k - da_chon); ++i) {
        chon[da_chon] = i;

        to_hop(chon, i + 1, da_chon + 1, k, n);
    }
}

/* Ban co doi xung qua truc doc, nen moi loi giai co mot loi giai
   guong. Chi can duyet nua so cot o HANG DAU TIEN roi nhan doi.

   Voi n le, cot giua phai xu ly rieng vi no la guong cua chinh no. */
int n_hau_doi_xung(int n)
{
    int q[32];
    int dem = 0;

    for (int cot = 0; cot < n / 2; ++cot) {
        q[0] = cot;
        dem += n_hau(q, 1, n);
    }

    dem *= 2;                     /* nhan doi cho nua ben kia */

    if (n % 2 == 1) {             /* cot giua, khong nhan doi */
        q[0] = n / 2;
        dem += n_hau(q, 1, n);
    }

    return dem;
}