八皇后問題動態圖形演示：回溯法與 BGI 圖形存取實作

編輯：關於C語言

經典演算法教學案例：八皇后問題 (8x8 棋盤擺放 8 個皇后，不共行/列/對角線) 動態視覺化演示，展示所有 92 組解。

演算法核心：回溯法與位元陣列優化

使用三個布林陣列標記攻擊範圍：

a[8]：列佔用標記 (a[col]=1 表示該列有皇后)
b[15]：主對角線佔用 (row+col 固定，索引 row+col)
c[15]：副對角線佔用 (row-col+7 固定，索引 row-col+7)

遞迴嘗試每行放置皇后：

void Try(int row) {
    for (int col = 0; col < 8; col++) {
        if (a[col] && b[row+col] && c[row-col+7]) { // 安全位置
            a[col] = b[row+col] = c[row-col+7] = 0; // 佔用
            DrawQueen(row, col);  // 繪製皇后圖形
            Delay(500);
            if (row < 7) Try(row + 1);
            else { ShowSolution(); Delay(3000); }
            a[col] = b[row+col] = c[row-col+7] = 1; // 回溯釋放
            EraseQueen(row, col); // 移除圖形
            Delay(500);
        }
    }
}

圖形存取技術：BGI 動態位圖

imagesize(x1,y1,x2,y2)：計算區域位圖大小。
malloc(size)：配置記憶體緩衝區。
getimage(x1,y1,x2,y2, buffer)：擷取螢幕區域至緩衝區 (皇冠圖形)。
putimage(x,y, buffer, COPY_PUT/XOR_PUT)：繪製/移除圖形 (XOR 模式可疊加還原背景)。

完整程式碼 (Turbo C)

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

char sol[3] = "00"; int a[8], b[15], c[15];
int queenRow[8] = {127,177,227,277,327,377,427,477};
int queenCol[8] = {252,217,182,147,112,77,42,7};
void* queenImg;

void Try(int r) {
    for (int c = 0; c < 8; c++)
        if (a[c] + b[r+c] + c[r-c+7] == 3) {
            a[c]=b[r+c]=c[r-c+7]=0;
            putimage(queenRow[r], queenCol[c], queenImg, COPY_PUT);
            delay(500);
            if (r < 7) Try(r+1);
            else { sol[1]++; if(sol[1]>'9'){sol[0]++;sol[1]='0';} bar(260,300,390,340); outtextxy(275,300,sol); delay(3000); }
            a[c]=b[r+c]=c[r-c+7]=1;
            putimage(queenRow[r], queenCol[c], queenImg, XOR_PUT);
            delay(500);
        }
}

int main() {
    int gd=DETECT, gm; initgraph(&gd,&gm,"");
    // 繪製皇冠圖形並 getimage 至 queenImg
    // 繪製 8x8 棋盤格線
    for(int i=0;i<=8;i++) line(125,i*35+5,525,i*35+5);
    for(int i=0;i<=8;i++) line(125+i*50,5,125+i*50,285);
    // 初始化標記陣列
    for(int i=0;i<8;i++) a[i]=1;
    for(int i=0;i<15;i++) b[i]=c[i]=1;
    Try(0); delay(3000); closegraph(); free(queenImg);
    return 0;
}