算法之美-回溯法与人工智能

算法之美-回溯法与人工智能n皇后问题研究的是如何将n个皇后放置在n�n的棋盘上,并且使皇后彼此之间不能相互攻击,(横竖和两个对角线方向均不会同时出现两个皇后)上图为8皇后问题的一种解法。给定一个整数n,返回所有不同的n皇后问题的解决方案。每一种解法包含一个明确的n皇后问题的棋子放置方案,该方案中'Q'和'.'分别代表了皇后和空位。示例:输入:4输出:[[".Q..",//解法1"...Q","Q....

算法之美-回溯法与人工智能

算法之美-回溯法与人工智能

n�皇后问题研究的是如何将 n�个皇后放置在 n�n 的棋盘上,并且使皇后彼此之间不能相互攻击,(横竖和两个对角线方向均不会同时出现两个皇后)

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的�n�皇后问题的解决方案。

每一种解法包含一个明确的�n 皇后问题的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4
输出: [
�[".Q..", �// 解法 1
� "...Q",
� "Q...",
� "..Q."],

�["..Q.", �// 解法 2
� "Q...",
� "...Q",
� ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;import java.util.List;public class NQueens { static boolean[] col; static boolean[] dia1; static boolean[] dia2; static List<List<String>> res;public static void main(String[] args) {int n = 4;res = new ArrayList<>();col = new boolean[n];dia1 = new boolean[2*n-1];dia2 = new boolean[2*n 1];LinkedList<Integer> row = new LinkedList<>();putQueen(n,0,row);System.out.println(res.toString());}// 尝试在一个n皇后问题中, 摆放第index行的皇后位置private static void putQueen(int n, int index, LinkedList<Integer> row) {// TODO Auto-generated method stubif(index==n) {res.add(generateBoard(n,row));return;}for(int i=0;i<n;i  ) { // 尝试将第index行的皇后摆放在第i列if(!col[i]&&!dia1[index i]&&!dia2[index-i n-1]) {row.addLast(i);col[i] = true;dia1[index i] = true;dia2[index-i n-1] = true;putQueen(n,index 1,row);col[i] = false;dia1[index i] = false;dia2[index-i n-1] = false;row.removeLast();}}}private static List<String> generateBoard(int n, LinkedList<Integer> row) {// TODO Auto-generated method stubassert row.size() == n;List<String> board = new ArrayList<>();for(int i =0;i<n;i  ) {char[] charArray = new char[n];Arrays.fill(charArray, '.');charArray[row.get(i)] = 'Q';board.add(new String(charArray));}return board;}}

类似人工只能问题

37. 解数独

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

数字�1-9�在每一行只能出现一次。
数字�1-9�在每一列只能出现一次。
数字�1-9�在每一个以粗实线分隔的�3x3�宫内只能出现一次。
空白格用�'.'�表示。

Note:

  • 给定的数独序列只包含数字�1-9�和字符�'.'�。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是�9x9�形式的。

源文地址:https://www.guoxiongfei.cn/csdn/5121.html