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

This article mainly introduces "how to use Java recursive backtracking to solve the problem of eight queens". In daily operation, I believe many people have doubts about how to use Java recursive backtracking to solve the problem of eight queens. Xiaobian consulted all kinds of data and sorted out simple and useful operation methods. I hope it will be helpful for you to answer the doubts of "how to use Java recursive backtracking to solve the problems of eight queens". Next, please follow the editor to study!

The problem of eight queens

The eight queens problem is an ancient and famous problem, and it is a typical case of backtracking algorithm. The problem was put forward by international chess player Max Bethel in 1848: put eight queens on 8X8 chess so that they could not attack each other, that is, no two queens could be on the same line, the same column or the same slash. Ask how many pendulums there are.

Solution idea

The first queen of ① puts the first row and the first column first.

The second queen of ② is placed in the first column of the second row, and then determines whether it is OK. If it is not 0K, continue to put it in the second column and the third column, and put all the columns in turn to find a suitable one.

③ continues to be the third queen, the first column and the second column. Until the eighth queen can also be placed in a non-conflict position, it is considered to have found a correct solution.

When ④ gets a correct solution, it will start backtracking when the stack goes back to the previous stack, that is, all the correct solutions that the first queen put in the first column will be obtained.

⑤ then goes back to the first queen to place the second column, and then continues to cycle through the steps of ①②③④.

Code implementation / * * @ Author: Yeman * @ Date: 2021-10-31-15:48 * @ Description: * / public class Queue8 {int max = 8; / 8 queens int [] arr = new int [max]; / / the subscript is the number (that is, the row), the value is the column static int count = 0; / / how many layouts static int judgeCount = 0 / / how many times public static void main (String [] args) {Queue8 queue8 = new Queue8 (); queue8.check (0); System.out.printf ("% d solutions\ n", count); System.out.printf ("% d times judged", judgeCount) } / / used to place the nth queen private void check (int n) {if (n = = max) {/ / n = 8 equals to the ninth queen, indicating that all the print (); return;} for (int I = 0; I) have been placed.

< arr.length; i++) { arr[n] = i; if (judge(n)){ //不冲突 check(n+1); } } } //用来第n个皇后判断与前面的所有皇后是否冲突 private boolean judge(int n){ judgeCount++; for (int i = 0; i < n; i++) { //是否同列同斜线 if (arr[i] == arr[n] || Math.abs(arr[i]-arr[n]) == Math.abs(i-n)){ return false; } } return true; } //输出每一种放法 private void print(){ count++; for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); }}运行结果 （截取部分）

At this point, the study on "how to use Java recursive backtracking to solve the problem of the eight queens" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.