Shulou(Shulou.com)06/02 Report--

This article is about how the C language uses backtracking to solve the eight queens problem. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

The backtracking method for solving the eight queens problem (N queens problem) I. description of the problem

Put eight queens on a chess board so that any two queens do not attack each other, find out all the chess methods and extend them to the case of N queens.

2. The source code # include#include#includeusing namespace std;void put_queen (int x, int y, vector&attack) {/ / implements the placement of queens in (XMagine y). Update the attack array. Xy indicates the coordinates of the queens, and attack indicates whether the queen / / direction array can be placed. It is convenient to mark the 8 directions later, static const int dx [] = {- 1lle Ling Ling 1m 0pm 1pm 1pm 1pm 1}. Attack [x] [y] = 1 attack / / Mark the position of the queen as 1 / / through a two-layer for loop, marking the position of the queen as for (int I = 1; I)

< attack.size(); i++)//从皇后位置向1到n-1个距离延伸 { for (int j = 0; j < 8; j++)//遍历8个方向 { int nx = x + i * dx[j];//生成的新位置行 int ny = y + i * dy[j];//生成的新位置列 //在棋盘范围内 if (nx >

= 0 & & nx

< attack.size() && ny >

= 0 & & ny

< attack.size()) attack[nx][ny] = 1;//标记为1 } }}//回溯算法//k表示当前处理的行//n表示n皇后问题//queen存储皇后的位置//attack标记皇后的攻击范围//solve存储N皇后的全部解法void backtrack(int k, int n, vector& queen, vector& attack, vector& solve){ if (k == n)//找到一组解 { solve.push_back(queen);//将结果queen存储至solve return; } //遍历0至n-1列，在循环中，回溯试探皇后可放置的位置 for (int i = 0; i < n; i++) { if (attack[k][i] == 0)//判断当前k行第i列是否可以放置皇后 { vector tmp = attack;//备份attack数组 queen[k][i] = 'Q';//标记该位置为Q put_queen(k, i, attack);//更新attack数组 backtrack(k + 1, n, queen, attack, solve);//递归试探k+1行的皇后的位置 attack = tmp;//恢复attack数组 queen[k][i] = '.';//恢复queen数组 } }}vectorsolveNQueens(int n){//string存储具体的摆放位置，存放一种解法，二维vector存放全部解法 vectorsolve;//存储最后结果 vectorattack;//标记皇后的攻击位 vectorqueen;//保存皇后位置 //使用循环初始化attack和queen数组 for (int i = 0; i < n; i++) { attack.push_back((vector())); for (int j = 0; j < n; j++) { attack[i].push_back(0); } queen.push_back(""); queen[i].append(n, '.'); } backtrack(0, n, queen, attack, solve); return solve;//返回结果数组}int main(){ //int num; //cin >

> num;// input queens to initialize attack array / / vector attack (num,vector (num, 0)); initialize queen array / / string s; / / for (int I = 0; I

< num; i++)s += '.'; //vector queen(num, s); int n; cin >

> n; vectorresult; result = solveNQueens (n); cout

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.