回溯法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

八皇后问题

#include <stdio.h>
#include <stdbool.h>
int g_number = 0;
void PrintQueen(int ColumnIndex[], int length)
{
printf("Solution %dn", g_number);
for(int i = 0; i < length; ++i)
printf("%dt", ColumnIndex[i]);
printf("n");
}
bool Check(int ColumnIndex[], int length)
{
for(int i = 0; i < length; ++ i)
{
for(int j = i + 1; j < length; ++ j)
{
if((i - j == ColumnIndex[i] - ColumnIndex[j])
|| (j - i == ColumnIndex[i] - ColumnIndex[j]))
return false;
}
}
return true;
}
void Permutation(int ColumnIndex[], int length, int index)
{
if(index == length)
{
if(Check(ColumnIndex, length))
{
++ g_number;
PrintQueen(ColumnIndex, length);
}
}
else
{
for(int i = index; i < length; ++ i)
{
int temp = ColumnIndex[i];
ColumnIndex[i] = ColumnIndex[index];
ColumnIndex[index] = temp;
Permutation(ColumnIndex, length, index + 1);
temp = ColumnIndex[index];
ColumnIndex[index] = ColumnIndex[i];
ColumnIndex[i] = temp;
}
}
}
void EightQueen()
{
const int queens = 8;
int ColumnIndex[queens];
for(int i = 0; i < queens; ++ i)
ColumnIndex[i] = i;
Permutation(ColumnIndex, queens, 0);
}
int main()
{
EightQueen();
return 0;
}

运行结果
Solution 1: 0 4 7 5 2 6 1 3
Solution 2: 0 5 7 2 6 3 1 4
Solution 3: 0 6 3 5 7 1 4 2
Solution 4: 0 6 4 7 1 3 5 2
Solution 5: 1 3 5 7 2 0 6 4
Solution 6: 1 4 6 3 0 7 5 2
Solution 7: 1 4 6 0 2 7 5 3
Solution 8: 1 5 0 6 3 7 2 4
Solution 9: 1 5 7 2 0 3 6 4
Solution 10: 1 6 2 5 7 4 0 3
Solution 11: 1 6 4 7 0 3 5 2
Solution 12: 1 7 5 0 2 4 6 3
Solution 13: 2 0 6 4 7 1 3 5
Solution 14: 2 4 1 7 0 6 3 5
Solution 15: 2 4 1 7 5 3 6 0
Solution 16: 2 4 6 0 3 1 7 5
Solution 17: 2 4 7 3 0 6 1 5
Solution 18: 2 5 3 0 7 4 6 1
Solution 19: 2 5 3 1 7 4 6 0
Solution 20: 2 5 1 4 7 0 6 3
Solution 21: 2 5 1 6 4 0 7 3
Solution 22: 2 5 1 6 0 3 7 4
Solution 23: 2 5 7 1 3 0 6 4
Solution 24: 2 5 7 0 4 6 1 3
Solution 25: 2 5 7 0 3 6 4 1
Solution 26: 2 6 1 7 4 0 3 5
Solution 27: 2 6 1 7 5 3 0 4
Solution 28: 2 7 3 6 0 5 1 4
Solution 29: 3 1 4 7 5 0 2 6
Solution 30: 3 1 6 4 0 7 5 2
Solution 31: 3 1 6 2 5 7 0 4
Solution 32: 3 1 6 2 5 7 4 0
Solution 33: 3 1 7 4 6 0 2 5
Solution 34: 3 1 7 5 0 2 4 6
Solution 35: 3 0 4 7 5 2 6 1
Solution 36: 3 0 4 7 1 6 2 5
Solution 37: 3 5 0 4 1 7 2 6
Solution 38: 3 5 7 1 6 0 2 4
Solution 39: 3 5 7 2 0 6 4 1
Solution 40: 3 6 2 7 1 4 0 5
Solution 41: 3 6 0 7 4 1 5 2
Solution 42: 3 6 4 2 0 5 7 1
Solution 43: 3 6 4 1 5 0 2 7
Solution 44: 3 7 0 2 5 1 6 4
Solution 45: 3 7 0 4 6 1 5 2
Solution 46: 3 7 4 2 0 6 1 5
Solution 47: 4 1 3 5 7 2 0 6
Solution 48: 4 1 3 6 2 7 5 0
Solution 49: 4 1 5 0 6 3 7 2
Solution 50: 4 1 7 0 3 6 2 5
Solution 51: 4 2 0 5 7 1 3 6
Solution 52: 4 2 0 6 1 7 5 3
Solution 53: 4 2 7 3 6 0 5 1
Solution 54: 4 0 3 5 7 1 6 2
Solution 55: 4 0 7 3 1 6 2 5
Solution 56: 4 0 7 5 2 6 1 3
Solution 57: 4 6 3 0 2 7 5 1
Solution 58: 4 6 0 3 1 7 5 2
Solution 59: 4 6 0 2 7 5 3 1
Solution 60: 4 6 1 3 7 0 2 5
Solution 61: 4 6 1 5 2 0 3 7
Solution 62: 4 6 1 5 2 0 7 3
Solution 63: 4 7 3 0 2 5 1 6
Solution 64: 4 7 3 0 6 1 5 2
Solution 65: 5 1 6 0 3 7 4 2
Solution 66: 5 1 6 0 2 4 7 3
Solution 67: 5 2 4 6 0 3 1 7
Solution 68: 5 2 4 7 0 3 1 6
Solution 69: 5 2 0 6 4 7 1 3
Solution 70: 5 2 0 7 4 1 3 6
Solution 71: 5 2 0 7 3 1 6 4
Solution 72: 5 2 6 3 0 7 1 4
Solution 73: 5 2 6 1 3 7 0 4
Solution 74: 5 2 6 1 7 4 0 3
Solution 75: 5 3 1 7 4 6 0 2
Solution 76: 5 3 0 4 7 1 6 2
Solution 77: 5 3 6 0 2 4 1 7
Solution 78: 5 3 6 0 7 1 4 2
Solution 79: 5 0 4 1 7 2 6 3
Solution 80: 5 7 1 3 0 6 4 2
Solution 81: 6 1 3 0 7 4 2 5
Solution 82: 6 1 5 2 0 3 7 4
Solution 83: 6 2 0 5 7 4 1 3
Solution 84: 6 2 7 1 4 0 5 3
Solution 85: 6 3 1 4 7 0 2 5
Solution 86: 6 3 1 7 5 0 2 4
Solution 87: 6 4 2 0 5 7 1 3
Solution 88: 6 0 2 7 5 3 1 4
Solution 89: 7 1 3 0 6 4 2 5
Solution 90: 7 1 4 2 0 6 3 5
Solution 91: 7 2 0 5 1 4 6 3
Solution 92: 7 3 0 2 5 1 6 4
分别表示皇后在每row的第col（solution的数字表示col的position）的位置。
详细的解释可以参考：回溯法与八皇后问题
说的很不错～

最后

以上就是复杂冬日为你收集整理的回溯法的全部内容，希望文章能够帮你解决回溯法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。