本文主要是介绍回溯法1——八皇后问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题：8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
思路：回溯法是一种试错方法：
1.先选一个位置试着放置一下，并做“记录”；
2.在每次子问题中进行判定时需要过去的“记录”作为是否可以继续尝试的依据；
3.最后很关键，需要在每次判断结束后将尝试位置进行复位，是为回溯。
#include<stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0//记录板，如果将一个皇后放上去，就只为TRUE
int board[8][8];//打印结果
void print_board(){int row;int column;static int n_solutions;n_solutions += 1;printf("Solution #%d:\n", n_solutions );for( row = 0; row < 8; row += 1 ){for( column = 0; column < 8; column += 1 ){if( board[ row ][ column ] )printf( " Q" );elseprintf( " +" );}putchar(10);}putchar(10);
}//关键函数，用来确认放置新皇后的位置是否与已有的冲突
//考虑到放置位置是逐行进行的，
//因此只需要检查上，左，左上，右上，四个方向有没有放过皇后
int conflicts( int row, int column ){int i;for(i=1;i<8;i+=1){//检查上，左，左上，右上，四个方向有没有放过皇后if(row-i>=0 && board[row-i][column ] )//上return TRUE;if( column-i>=0&&board[ row ][ column-i])//左return TRUE;if(row-i>=0&&column-i>=0&& board[ row-i][column-i])//左上return TRUE;if(row-i>=0&&column+i<8&& board[ row-i][column+i])//右上return TRUE;}//如果上，左，左上，右上，四个方向均未放过皇后，则该位置不冲突return FALSE;
}//关键函数：用来对新皇后进行放置
void place_queen( int row ){int column;//对于第row行的colum个位置，逐列进行试探。for( column = 0; column < 8; column += 1 ){逐列进行测试board[ row ][ column ] = TRUE;试着置为1//如果位置[row，column] 不冲突，就说明可以试探放置if( row == 0 || !conflicts( row, column ) ){if(row<7)//还未到头place_queen( row+1);else//一个放置方案完成了。print_board();}//逻辑难点：记得试探过后再回溯回去，保证复位。board[ row ][ column ] = FALSE;测试后置回0}
}
int
main(){place_queen( 0 );return EXIT_SUCCESS;
}这篇关于回溯法1——八皇后问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
