C语言回溯算法之八皇后、迷宫、素数环、数独
昨天中午，因玩了一把数独，突然间就勾起了我对回溯算法的回忆，于是乎，将几个经典的回溯算法的例子写了一遍，记录一下。
1、八皇后
问题描述：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
解题思路：最简单的做法就是穷举法，将8^8 =16,777,216 种情况全部穷举一遍，判断是否符合要求，显然这种方法太过于耗费时间，不可取，于是引入了回溯算法，虽然回溯算法也是暴力搜索，但是优于穷举法。思路是，先将第一列放上一个皇后，在第二列不冲突的位置上放上另一个皇后，在第三列不冲突的位置放上第三个皇后，依次类推，如果下一个皇后没有一个安放的位置，则返回上一步，放在第二个不冲突的位置上，如果不满足，依次退回。简单的C语言代码如下所示：
char Board[N + 2][N + 2] ; //! 棋盘数组int SolveCount = 0 ; //! 解法计数//! 打印显示棋盘void Display_Board(void){int row , col ;for(row = 0 ; row < N + 2 ; ++ row){for(col = 0 ; col < N + 2 ; ++ col){printf(" %c" , Board[row][col]) ;}printf("\n") ;}}//! 初始化棋盘void Init_Board(void){int row , col ;for(row = 0 ; row < N + 2 ; ++ row){for(col = 0 ; col < N + 2 ; ++ col){if(row > 0 && row < N + 1 && col > 0 && col < N + 1)Board[row][col] = ' ' ;elseBoard[row][col] = '#' ;}}}//! 检测该位置的皇后是否冲突int Check_Board(int row , int col){int nCol = col - 1 , nCol1 = col + 1 ;for(-- row ; row > 0 ; -- row , -- nCol , ++ nCol1){if(Board[row][col] == '*') return 0 ;if(nCol > 0){if(Board[row][nCol] == '*') return 0 ;}if(nCol1 < N + 1){if(Board[row][nCol1] == '*') return 0 ;}}return 1;}//! 求解棋盘void Solve_Boad(int row){if(row > N) //! 判断是否所有位置已安放完成{SolveCount ++ ;printf("Solution: %d\n" , SolveCount) ;Display_Board() ;getchar() ; //! 按下Enter键获取下一种解法}else{int col = 1;for( ; col <= N ; ++ col){if(Check_Board(row , col)){Board[row][col] = '*' ;Solve_Boad(row + 1) ;Board[row][col] = ' ' ;}}}}int main(){Init_Board() ;Solve_Boad(1) ;return 0;}
2、迷宫
问题描述：在一堆复杂的建筑物中，找到一条，由入口通向出口的道路。
解题思路：用程序解迷宫时，为了简化迷宫，采用二维数组表示，0表示可以通过，1表示不可以通过，#表示墙，*表示最后的路径，首先从入口开始寻找下一个可以走的位置，如有合适的位置，继续向前，否则退回到上一步，选择下一个合适的位置，依次类推，直到找到最后一个出口位置，代码如下：
#include <stdio.h>#include <stdlib.h>#define ROW 10#define COL 10int SolveCount = 0 , AllStep = 0 ; //! 解法计数 步骤计数char MazeArr[ROW + 2][COL + 2] = //! 迷宫数组，0表示可走，1表示不可走{{'#','#','#','#','#','#','#','#','#','#','#','#'} ,{'#','0','0','1','1','1','0','0','0','1','1','#'} ,{'#','1','0','1','1','1','0','1','0','0','0','#'} ,{'#','1','0','1','1','1','0','1','0','1','0','#'} ,{'#','1','0','0','0','0','0','1','0','1','0','#'} ,{'#','1','1','1','0','1','1','1','0','0','0','#'} ,{'#','1','0','0','0','0','1','1','0','1','0','#'} ,{'#','1','0','1','1','0','0','0','0','1','0','#'} ,{'#','1','0','1','1','0','1','1','1','0','0','#'} ,{'#','1','0','0','0','0','1','1','1','0','1','#'} ,{'#','1','1','1','1','1','1','1','1','0','0','#'} ,{'#','#','#','#','#','#','#','#','#','#','#','#'} ,} ;//! 打印显示迷宫盘数据void Display_Maze(void){int row , col ;for(row = 0 ; row < ROW + 2 ; ++ row){for(col = 0 ; col < COL + 2 ; ++ col){printf(" %c" , MazeArr[row][col]) ;}printf("\n") ;}}const int Position[4][2] = { {-1 , 0} , {0 , 1} , {1 , 0} , {0 , -1} };//! 检测该位置的可走方向，记录可走的位置int Check_Maze(int pos , int dire , int * nPos){int row = pos / (ROW + 2) , col = pos % (ROW + 2) , nRow , nCol ;nRow = row + Position[dire][0] ; nCol = col + Position[dire][1] ;if(MazeArr[nRow][nCol] == '0') { * nPos = nRow * (ROW + 2) + nCol ; return 1 ;}return 0 ;}//! 求解迷宫void Solve_Maze(int pos){if(pos == ROW * (COL + 2) + COL ) //! 判断是否到达目的地{SolveCount ++ ; MazeArr[ROW][COL] = '*' ;printf("Solution: %d Step: %d\n" , SolveCount , AllStep) ;Display_Maze() ; MazeArr[ROW][COL] = '0' ;getchar() ; //! 按下Enter键获取下一个解法}else{int dire = 0 , nPos ;for( ; dire < 4 ; ++ dire) //! 轮流检测4个方位是否可走{if(Check_Maze(pos , dire , &nPos)) //! 判断该方向是否可走{int row = pos / (ROW + 2) , col = pos % (ROW + 2) ;MazeArr[row][col] = '*' ; AllStep ++ ;Solve_Maze(nPos) ;MazeArr[row][col] = '0' ; AllStep -- ;}}}}int main(){Solve_Maze(1 * (COL + 2) + 1) ;return 0;}
3、素数环
问题描述：将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。
例如：n=20时，下面的序列就是一个素数环：
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18
解题思路：创建一个长度为N的一维数组，初始化数组为0，然后采用回溯算法依次安放下一个位置的数字，直到所有数据安放完成。代码如下：
int SolveCount = 0 ; //! 解法计数int PrimeArr[N] ; //! 素数环数组//! 素数环数初始化void Prime_Arr_Init(void){int n = 0 ;for( ; n < N ; ++ n) PrimeArr[n] = 0 ;}//! 打印显示素数环void Dosplay_Prime_Ring(void){int n = 0 ;for( ; n < N ; ++ n) printf(" %d" , PrimeArr[n]) ;printf("\n") ;}//! 判断是否是素数int isPrime(int num){int i = 2 ;double k = sqrt(num) ;for( ; i <= k ; ++ i ){if(num % i == 0) return 0 ;}return 1 ;}//! 检测素数环数据是否满足要求int Check_Prime_Ring(int index , int num){int n = 0 , sum ;//! 判断这个数字之前的位置是否已经使用for( ; n < index ; ++ n){if(PrimeArr[n] == num) return 0 ;}//! 当是最后一个位置的时候，需要判断和环首的和是否为素数if(index == N - 1){sum = num + PrimeArr[0] ;if(!isPrime(sum)) return 0 ;}//! 计算和前领居的和sum = num + PrimeArr[index - 1] ;return isPrime(sum) ;}//! 求解素数环void Solve_Prime_Ring(int index){if(index == N){SolveCount ++ ;printf("Solution: %d\n" , SolveCount) ;Dosplay_Prime_Ring() ;getchar() ; //! 按下Enter键获取下一个解法}else{int num = 1 ;for( ; num <= N ; ++ num){if(Check_Prime_Ring(index , num)){PrimeArr[index] = num ;Solve_Prime_Ring(index + 1) ;PrimeArr[index] = 0 ;}}}}int main(){Prime_Arr_Init() ;Solve_Prime_Ring(0) ;return 0;}
4、数独
问题描述：数独是源自于18世纪瑞士的一种数学游戏，是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9不重复。数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
解题思路：为了简化模型，采用一个9*9的二维数组表示数独表，每一个格的数据填写在对应的数组中，未知的数字用0表示，采用回溯法暴力搜索，代码如下所示：
int SolveCount = 0 ; //! 解法计数//! 需要求解的数独数据 0表示未知数，需要求解的值，不同的数独，修改此数组的值int SudokuArr[9][9] ={{0 , 0 , 4 , 2 , 5 , 0 , 0 , 0 , 0 } ,{0 , 0 , 1 , 0 , 0 , 4 , 9 , 0 , 0 } ,{9 , 0 , 0 , 0 , 0 , 8 , 0 , 0 , 0 } ,{0 , 0 , 0 , 0 , 3 , 1 , 0 , 0 , 0 } ,{0 , 0 , 0 , 9 , 0 , 2 , 0 , 0 , 0 } ,{3 , 0 , 9 , 0 , 8 , 0 , 0 , 7 , 0 } ,{0 , 1 , 0 , 0 , 0 , 6 , 0 , 0 , 0 } ,{0 , 5 , 0 , 0 , 0 , 7 , 0 , 6 , 0 } ,{6 , 9 , 0 , 0 , 0 , 3 , 0 , 0 , 0 } ,} ;//! 打印显示数独void Display_Sudoku(void){int row , col ;for(row = 0 ; row < 9 ; ++ row){for(col = 0 ; col < 9 ; ++ col)printf(" %d" , SudokuArr[row][col]) ;printf("\n") ;}}//! 寻找下一个需要填的空位int Find_Next_Empty(int * pos){int row , col ;for(row = 0 ; row < 9 ; ++ row){for(col = 0 ; col < 9 ; ++ col){if(SudokuArr[row][col] == 0){* pos = row * 9 + col ;return 1 ;}}}return 0 ;}//! 检查该位置的数字是否满足要求，1 满足 0 不满足int Check_Sudoku(int pos , int num){int row = pos / 9 , col = pos % 9 , i , j , x , y ;//! 判断行重复for(i = 0 ; i < 9 ; ++ i){if(SudokuArr[row][i] == num) return 0;}//! 判断列重复for(i = 0 ; i < 9 ; ++ i){if(SudokuArr[i][col] == num) return 0;}//! 判断小九宫格重复x = col / 3 * 3 ; y = row / 3 * 3 ;for(i = 0 ; i < 3 ; ++ i){for(j = 0 ; j < 3 ; ++ j){if(SudokuArr[y + i][x + j] == num) return 0 ;}}return 1 ; //! 无重复，满足要求}//! 求解数独void Solve_Sudoku(void){int pos ;if(!Find_Next_Empty(&pos)) //! 判断是否填完{SolveCount ++ ;printf("Solution: %d\n" , SolveCount) ;Display_Sudoku() ;getchar() ; //! 按下Enter键获取下一个解法}else{int num = 1 ;for( ; num < 10 ; ++ num){if(Check_Sudoku(pos , num)) //! 判断该值是否满足要求{int row = pos / 9 , col = pos % 9 ;SudokuArr[row][col] = num ;Solve_Sudoku() ;SudokuArr[row][col] = 0 ;}}}}int main(){Solve_Sudoku() ;return 0;}