亲宝软件园·资讯

展开

递归回溯法求N皇后问题

七月的四字 人气:0
>问题描述:在一个N*N(比如4*4)的方格中,在每一列中放置一个皇后,要求放置的皇后不在同一行,同一列,同一斜线上,求一共有多少种放置方法,输出放置的数组。 >思路解析:从(1,1)开始,一列一列的放置皇后,第一列放置在(1,1)。第二列(1,2)不行,(2,2)不行,(2,3)可以,自此第2列放置完成。第三列依次判断。 可以看到对于第j列都要从第一行开始判断(1,j),(2,j),(3,j)...(N,j)。如果有一个满足则暂停该列,向后判断下一列,(1,j+1),(2,j+1),(3,j+1)...(N,j+1), 同样出现第一个满足放置的(i,j+1)就要暂停该列,继续向下一列,直到第N列。第N列判断完成后,返回N-1列继续执行(i,N-1),(i+1,N-1)...可以看出每一列都要重复 判断,可以考虑递归算法queen(int column,int(*a)N) 在queen中若column=N-1(有下标),则全局变量number++,输出二维数组a,当递归返回时,注意恢复数值为0, 比如suit(i,column,a)满足放置条件,则递归进入queen(column+1,a),返回后要令a[i][column]==0; ``` #include #include #include //判断点(i,j)是否合适 bool suit(int m, int n,int (*a)[4]) { int i, j; for (j = 0; j < 4; j++) {//判断同一行 if (a[m][j] == 1&&j!=n) return false; } for (i = 0; i < 4; i++) {//判断同一列 if (a[i][n] == 1&&i!=m) return false; } for ( i = m - 1, j = n - 1; i >= 0&& j >= 0; i--, j--) { if (a[i][j] == 1) { return false; } } for ( i = m + 1, j = n - 1; i < 4&&j >= 0; i++, j--) { if (a[i][j] == 1) { return false; } } } void queen(int number,int column,int (*a)[4]) { if (column == 4) { for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { printf_s("%d", a[i][j]); } printf_s("\n"); number++; } } for (int i = 0; i <4; i++) { if (suit(i, column,a)) { a[i][column] = 1; queen(number,column+1, a);//从这里返回 a[i][column] = 0; } } } int main() { int a[4][4]; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { a[i][j] = 0; } } static int number = 0; queen(number,0, a); system("pause"); } ``` >[代码借鉴](https://www.cnblogs.com/xumenger/p/4311970.html)

加载全部内容

相关教程
猜你喜欢
用户评论