1、九宫格

算法规则：

1. 把 1 放到第一行的中间
2. 开始向右上角放入后面的数字
   1. 如果右上是空的，直接填入
   2. 如果右上已经填过了，直接填在当前位置的下面
   3. 如果右上角超出了边界，那么放在右边的最下面或是最左边。也就是超出了边界了，就在边界的另外一头填入。

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