1、九宫格
算法规则：
- 把 1 放到第一行的中间
- 开始向右上角放入后面的数字
- 如果右上是空的，直接填入
- 如果右上已经填过了，直接填在当前位置的下面
- 如果右上角超出了边界，那么放在右边的最下面或是最左边。也就是超出了边界了，就在边界的另外一头填入。
1.png
代码实现
/**
* 九宫格的回溯法
*
* @param array
* @return
*/
public int[][] squaredUp(int[][] array) {
int n = array.length;
int x = 1; //要填入的数据
//定义起始位置
int row = 0;
int col = n / 2;
array[row][col] = x;
while (x < n * n) {
//在选择下一位置的时候，先记录下现在的位置
int tempRow = row, tempCol = col;
//向右上移动
row--;
if (row < 0) { //如果上面超出边界了，那么row赋值为：右边最下面的一行，即：n-1
row = n - 1;
}
col++;
if (col == n) { //如果右边超出边界了，那么col还原为：1
col = 0;
}
//下一个值
x++;
if (array[row][col] == 0) { //如果没有填值，则直接赋值
array[row][col] = x;
} else { //如果已经填值，就放在当前位置的下面
//还原
row = tempRow;
col = tempCol;
row++;
array[row][col] = x;
}
}
return array;
}
测试及结果
@Test
public void main() {
int n = 5;
int[][] array = new int[n][n];
array = squaredUp(array);
System.out.println("5 * 5 的九宫格算法矩阵图：");
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println();
}
}
结果：
5 * 5 的九宫格算法矩阵图：
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
2、八皇后
3.png
代码实现
/**
* 回溯法之八皇后
* author: bobo
* create time: 2019/1/22 4:14 PM
* email: jqbo84@163.com
*/
public class EightQueen {
public static int SIZE = 8;
public static int[] array = new int[SIZE];
/**
* 八皇后算法
*/
public void eightQueens() {
eightQueens(0);
}
public void eightQueens(int row) {
//如果有结果了就退出
if(row == 8){
printResult();
System.out.println("---------------");
return;
}
//开始从第一列到最后一列一个个放入
for (int col = 0; col < SIZE; col++) {
array[row] = col;
if (judge(row)) { //判断是否可以放入
eightQueens(row + 1); //就开始下一行
}
}
}
/**
* 判断当前列放入的位置是否和以前放过的内容有冲突
*
* @param n
* @return
*/
public boolean judge(int n) {
for (int i = 0; i < n; i++) {
//条件1：array[n] == array[i] 表示在一列上
//条件2：abs(array[n] - array[i]) == abs(n-i) 表示在对角线上
if (array[n] == array[i] || Math.abs(array[n] - array[i]) == Math.abs(n - i)) {
return false;
}
}
return true;
}
public static void printResult(){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
}
测试结果
@Test
public void main(){
eightQueens();
}
结果：
0 4 7 5 2 6 1 3
---------------
0 5 7 2 6 3 1 4
---------------
0 6 3 5 7 1 4 2
---------------
0 6 4 7 1 3 5 2
---------------
1 3 5 7 2 0 6 4
---------------
1 4 6 0 2 7 5 3
---------------
......
3、数独
/**
* 回溯法之数独问题
* author: bobo
* create time: 2019/1/22 5:14 PM
* email: jqbo84@163.com
*/
public class Sudoku {
public static int SIZE = 9;
public static int[][] array = new int[][]{
{8, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 3, 6, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 9, 0, 2, 0, 0},
{0, 5, 0, 0, 0, 7, 0, 0, 0},
{0, 0, 0, 0, 4, 5, 7, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 3, 0},
{0, 0, 1, 0, 0, 0, 0, 6, 8},
{0, 0, 8, 5, 0, 0, 0, 1, 0},
{0, 9, 0, 0, 0, 0, 4, 0, 0}
};
public static void sudoku() {
sudoku(0, 0);
}
public static void sudoku(int i, int j) {
if (i == 8 && j == 9) {
printResult();
return;
}
if (j == 9) {//横着放的时候，如果到了最右边，就回到下一行的第一个
j = 0;
i++;
}
if (array[i][j] == 0) { //如果是空的
for (int k = 1; k <= SIZE; k++) {
if (judge(i, j, k)) {
array[i][j] = k;
sudoku(i, j + 1);
//让前一次的格子还原
array[i][j] = 0;
}
}
} else {
sudoku(i, j + 1);
}
}
/**
* 判断当前位置上是否可以放入数字
*
* @param row
* @param col
* @param number
* @return
*/
public static boolean judge(int row, int col, int number) {
//判断行和列不重复
for (int i = 0; i < SIZE; i++) {
if (array[row][i] == number || array[i][col] == number) {
return false;
}
}
//判断自己所在的宫里面没有重复值
int tempRow = row / 3;
int tempCol = col / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (array[tempRow * 3 + i][tempCol * 3 + j] == number) {
return false;
}
}
}
return true;
}
public static void printResult() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println();
}
System.out.println("-----------------");
}
}
测试及结果
@Test
public void main() {
sudoku();
}
结果：
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
网友评论