package cn.iocoder.yudao.framework.common.thealgorithms.backtracking;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

///*
//    * Problem Statement: -
//
//    Given a N*N board with the Knight placed on the first block of an empty board. Moving according
//   to the rules of chess knight must visit each square exactly once. Print the order of each cell in
//   which they are visited.
//
//    Example: -
//
//    Input : N = 8
//
//    Output:
//        0  59  38  33  30  17   8  63
//        37  34  31  60   9  62  29  16
//        58   1  36  39  32  27  18   7
//        35  48  41  26  61  10  15  28
//        42  57   2  49  40  23   6  19
//        47  50  45  54  25  20  11  14
//        56  43  52   3  22  13  24   5
//        51  46  55  44  53   4  21  12
//
// */
//public final class KnightsTour {
//    private KnightsTour() {
//    }
//
//    private static final int BASE = 12;
//    private static final int[][] MOVES = {
//        {1, -2},
//        {2, -1},
//        {2, 1},
//        {1, 2},
//        {-1, 2},
//        {-2, 1},
//        {-2, -1},
//        {-1, -2},
//    }; // Possible moves by knight on chess
//    private static int[][] grid; // chess grid
//    private static int total; // total squares in chess
//
//    public static void main(String[] args) {
//        grid = new int[BASE][BASE];
//        total = (BASE - 4) * (BASE - 4);
//
//        for (int r = 0; r < BASE; r++) {
//            for (int c = 0; c < BASE; c++) {
//                if (r < 2 || r > BASE - 3 || c < 2 || c > BASE - 3) {
//                    grid[r][c] = -1;
//                }
//            }
//        }
//
//        int row = 2 + (int) (Math.random() * (BASE - 4));
//        int col = 2 + (int) (Math.random() * (BASE - 4));
//
//        grid[row][col] = 1;
//
//        if (solve(row, col, 2)) {
//            printResult();
//        } else {
//            System.out.println("no result");
//        }
//    }
//
//    // Return True when solvable
//    private static boolean solve(int row, int column, int count) {
//        if (count > total) {
//            return true;
//        }
//
//        List<int[]> neighbor = neighbors(row, column);
//
//        if (neighbor.isEmpty() && count != total) {
//            return false;
//        }
//
//        neighbor.sort(Comparator.comparingInt(a -> a[2]));
//
//        for (int[] nb : neighbor) {
//            row = nb[0];
//            column = nb[1];
//            grid[row][column] = count;
//            if (!orphanDetected(count, row, column) && solve(row, column, count + 1)) {
//                return true;
//            }
//            grid[row][column] = 0;
//        }
//
//        return false;
//    }
//
//    // Returns List of neighbours
//    private static List<int[]> neighbors(int row, int column) {
//        List<int[]> neighbour = new ArrayList<>();
//
//        for (int[] m : MOVES) {
//            int x = m[0];
//            int y = m[1];
//            if (grid[row + y][column + x] == 0) {
//                int num = countNeighbors(row + y, column + x);
//                neighbour.add(new int[] {row + y, column + x, num});
//            }
//        }
//        return neighbour;
//    }
//
//    // Returns the total count of neighbors
//    private static int countNeighbors(int row, int column) {
//        int num = 0;
//        for (int[] m : MOVES) {
//            if (grid[row + m[1]][column + m[0]] == 0) {
//                num++;
//            }
//        }
//        return num;
//    }
//
//    // Returns true if it is orphan
//    private static boolean orphanDetected(int count, int row, int column) {
//        if (count < total - 1) {
//            List<int[]> neighbor = neighbors(row, column);
//            for (int[] nb : neighbor) {
//                if (countNeighbors(nb[0], nb[1]) == 0) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    // Prints the result grid
//    private static void printResult() {
//        for (int[] row : grid) {
//            for (int i : row) {
//                if (i == -1) {
//                    continue;
//                }
//                System.out.printf("%2d ", i);
//            }
//            System.out.println();
//        }
//    }
//}
//

/*
 * 问题陈述：-
 *
 * 给定一个N*N的棋盘，骑士放在空棋盘的第一个方块上。根据国际象棋骑士的规则移动，
 * 必须恰好访问每个方格一次。打印每个单元格被访问的顺序。
 *
 * 示例：-
 *
 * 输入：N = 8
 *
 * 输出：
 *     0  59  38  33  30  17   8  63
 *     37  34  31  60   9  62  29  16
 *     58   1  36  39  32  27  18   7
 *     35  48  41  26  61  10  15  28
 *     42  57   2  49  40  23   6  19
 *     47  50  45  54  25  20  11  14
 *     56  43  52   3  22  13  24   5
 *     51  46  55  44  53   4  21  12
 *
 */
public final class KnightsTour {
    private KnightsTour() {
    }

    private static final int BASE = 12; // 基础大小
    private static final int[][] MOVES = { // 骑士在棋盘上可能的移动
            {1, -2},
            {2, -1},
            {2, 1},
            {1, 2},
            {-1, 2},
            {-2, 1},
            {-2, -1},
            {-1, -2},
    };
    private static int[][] grid; // 棋盘网格
    private static int total; // 棋盘上的总方格数

    public static void main(String[] args) {
        grid = new int[BASE][BASE];
        total = (BASE - 4) * (BASE - 4); // 计算总方格数

        // 初始化棋盘边界
        for (int r = 0; r < BASE; r++) {
            for (int c = 0; c < BASE; c++) {
                if (r < 2 || r > BASE - 3 || c < 2 || c > BASE - 3) {
                    grid[r][c] = -1;
                }
            }
        }

        // 随机选择起始位置
        int row = 2 + (int) (Math.random() * (BASE - 4));
        int col = 2 + (int) (Math.random() * (BASE - 4));

        grid[row][col] = 1; // 设置起始位置

        // 如果找到解决方案，则打印结果
        if (solve(row, col, 2)) {
            printResult();
        } else {
            System.out.println("无结果");
        }
    }

    // 当找到解决方案时返回True
    private static boolean solve(int row, int column, int count) {
        if (count > total) {
            return true;
        }

        List<int[]> neighbor = neighbors(row, column);

        // 如果没有邻居且计数不等于总数，则返回false
        if (neighbor.isEmpty() && count != total) {
            return false;
        }

        // 根据邻居数量排序
        neighbor.sort(Comparator.comparingInt(a -> a[2]));

        // 遍历所有邻居
        for (int[] nb : neighbor) {
            row = nb[0];
            column = nb[1];
            grid[row][column] = count;
            // 如果没有孤立点且递归求解成功，则返回true
            if (!orphanDetected(count, row, column) && solve(row, column, count + 1)) {
                return true;
            }
            grid[row][column] = 0; // 回溯
        }

        return false;
    }

    // 返回邻居列表
    private static List<int[]> neighbors(int row, int column) {
        List<int[]> neighbour = new ArrayList<>();

        // 检查所有可能的移动
        for (int[] m : MOVES) {
            int x = m[0];
            int y = m[1];
            if (grid[row + y][column + x] == 0) {
                int num = countNeighbors(row + y, column + x);
                neighbour.add(new int[] {row + y, column + x, num});
            }
        }
        return neighbour;
    }

    // 返回邻居的总数
    private static int countNeighbors(int row, int column) {
        int num = 0;
        for (int[] m : MOVES) {
            if (grid[row + m[1]][column + m[0]] == 0) {
                num++;
            }
        }
        return num;
    }

    // 如果是孤立点则返回true
    private static boolean orphanDetected(int count, int row, int column) {
        if (count < total - 1) {
            List<int[]> neighbor = neighbors(row, column);
            for (int[] nb : neighbor) {
                if (countNeighbors(nb[0], nb[1]) == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    // 打印结果网格
    private static void printResult() {
        for (int[] row : grid) {
            for (int i : row) {
                if (i == -1) {
                    continue;
                }
                System.out.printf("%2d ", i);
            }
            System.out.println();
        }
    }
}
