回溯算法的經(jīng)典例題。大一的時(shí)候就有耳聞，卻一直沒有實(shí)現(xiàn)，今天終于有機(jī)會把它寫出來，小有成就感啊。
這里算法采用的是深度優(yōu)先搜索，從第一個(gè)節(jié)點(diǎn)開始，按行優(yōu)先的原則逐個(gè)掃描每個(gè)點(diǎn)，如果該點(diǎn)合法，可以選擇放一個(gè)queen也可以選擇不放，當(dāng)該點(diǎn)不合法時(shí)，就跳過該點(diǎn)接著判斷下一個(gè)點(diǎn)。
有人把回溯算法說成是“萬能算法”，這么說的原因是回溯實(shí)際上就是枚舉，它的最壞情況始終是指數(shù)或階乘級的。對它的優(yōu)化主要體現(xiàn)在約“約束函數(shù)”和“限界函數(shù)”這兩個(gè)剪枝函數(shù)上。
我曾經(jīng)嘗試用回溯寫過背包，結(jié)果是無情的超時(shí)，與動態(tài)規(guī)劃的O(NV)來說，回溯O(2^N)的時(shí)間復(fù)雜度真是不敢恭維。因此對回溯有些“偏見”。但是前面說過了，回溯的剪枝是很重要的，剪枝函數(shù)做的好可以在實(shí)際中大大降低回溯的時(shí)間復(fù)雜度。
下面是我八皇后問題的代碼：

#include<stdio.h>//eight queens
#include<string.h>
#include<stdlib.h>
#define LEN 100
int mp[LEN][LEN];
int len;
int nq;
long long count;
long long countall;
int canput(int x, int y)
{
    int i, j;
    if(mp[x][y] == 1)
        return 0;
    for(i = 0; i < len; i++)
    {
        if(mp[x][i] == 1 || mp[i][y] == 1)
            return 0;
    }
    for(i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--)
        if(mp[i][j] == 1)
            return 0;
    for(i = x + 1, j = y + 1; i < len && j < len; i++, j++)
        if(mp[i][j] == 1)
            return 0;

    for(i = x - 1, j = y + 1; i >= 0 && j < len; i--, j++)
        if(mp[i][j] == 1)
            return 0;
    for(i = x + 1, j = y - 1; i < len && j >= 0; i++, j--)
        if(mp[i][j] == 1)
            return 0;
    return 1;
}
void DFS(int m)
{
    countall++;
    int i, j;
    if(m < len * len)
    {
        int x = m / len;
        int y = m % len;
        if(canput(x, y) == 1)//can put queen in this point
        {
            nq++;
            mp[x][y] = 1;
            DFS(m + 1);
            mp[x][y] = 0;
            nq--;
            
            DFS(m + 1);
        }
        else//can not put queen in this point
            DFS(m + 1);
    }
    else if(nq == len)
    {
        count++;
        printf("out end map[][]:\n");
        for(i = 0; i < len; i++)
        {
            for(j = 0; j < len; j++)
                printf("%d ", mp[i][j]);
            putchar(10);
        }
    }
}
int main()
{
    int i, j;
    len = 8;
    for(i = 0; i < len; i++)
        for(j = 0; j < len; j++)
            mp[i][j] = 0;
    count = 0;
    nq = 0;
    countall = 0;
    DFS(0);
    printf("count = %ld\n", count);
    //printf("countall = %ld\n", countall);
    system("pause");
    return 0;
}

看了書上的代碼才發(fā)現(xiàn)自己寫的效率不高。上面我寫的是從棋盤的第一個(gè)位置開始，依次判每一個(gè)位置。事實(shí)上，只要這一行有皇后，該行的其余地方就不能放了，我之前的做法無疑增加了分支個(gè)數(shù)。還有，我的限界函數(shù)寫的太沒技術(shù)含量，看完書上利用斜率寫限界函數(shù)時(shí)，真是感覺很慚愧啊。
以下是書上的經(jīng)典算法，可與上面的算法對比一下，效率差距很明顯。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 20
#define LENQ 8
int x[LEN];
int sum;
int Mabs(int a)
{
    if(a < 0)
        return -a;
    return a;
}
int Place(int k)
{
    for(int j = 1; j < k; j++)
        if(Mabs(k - j) == Mabs(x[j] - x[k]) || x[j] == x[k])
            return 0;
    return 1;
}
void Queen(int t)
{
    if(t > LENQ)
    {
        sum++;
        for(int i = 1; i <= LENQ; i++)
            printf("%d ", x[i]);
        putchar(10);
    }
    else
        for(int i = 1; i <= LENQ; i++)
        {
            x[t] = i;
            if(Place(t))
                Queen(t + 1);
        }
}
int main()
{
    int i, j;
    sum = 0;
    Queen(1);
    printf("sum = %d\n", sum);
    system("pause");
}