1 package leetcode_2020; 2 3 /* 4 *https://leetcode-cn.com/problems/n-queens/ 5 6 *n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 7 * 给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。 8 9 每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q‘ 和 ‘.‘ 分别代表了皇后和空位。 10 11 * */ 12 import java.util.LinkedList; 13 import java.util.List; 14 15 public class code051_N_Queens 16 { 17 18 List<List<String>> result = new LinkedList<>(); 19 public int totalNQueens(int n) { 20 result = solveNQueens(n); 21 return result.size(); 22 } 23 public List<List<String>> solveNQueens(int n) { 24 char[][] board = new char[n][n]; 25 for(int i = 0; i < n; i++){ 26 for(int j = 0; j < n; j++){ 27 board[i][j] = ‘.‘; 28 } 29 } 30 backpack(board, 0); 31 return result; 32 } 33 34 public void backpack(char[][] board, int row){ 35 if(board.length == row){ 36 List<String> list = new LinkedList<>(); 37 for (char[] s: board) 38 { 39 list.add(String.valueOf(s)); 40 } 41 result.add(list); 42 return; 43 } 44 for(int col = 0; col < board.length; col++){ 45 if(!isvalid(board, row, col)){ 46 continue; 47 } 48 board[row][col] = ‘Q‘; 49 backpack(board, row + 1); 50 board[row][col] = ‘.‘; 51 } 52 } 53 public boolean isvalid(char[][] board, int row, int col){ 54 55 for(int i = 0; i < board.length; i++){ 56 if(board[i][col] == ‘Q‘){ 57 return false; 58 } 59 } 60 for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){ 61 if(board[i][j] == ‘Q‘) 62 return false; 63 } 64 for(int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++){ 65 if(board[i][j] == ‘Q‘) 66 return false; 67 } 68 return true; 69 } 70 71 public static void main(String[] args){ 72 code051_N_Queens n_queens = new code051_N_Queens(); 73 // System.out.println(n_queens.solveNQueens(4)); 74 System.out.println(n_queens.totalNQueens(4)); 75 } 76 }
原文:https://www.cnblogs.com/Z-D-/p/12630999.html