算法分析---8皇后问题---N皇后问题

一时失言乱红尘 2022-11-16 05:51 186阅读 0赞

![在这里插入图片描述][20210406171121133.png]

package demo1;
    
    public class NkingsSort {
        
    
        public static int num1(int n) {
        
            if (n < 1) {
        
                return 0;
            }
            int[] record = new int[n];
            return process1(0, record, n);
        }
    
        public static int process1(int i, int[] record, int n) {
        
            if (i == n) {
        
                return 1;
            }
            int res = 0;
            for (int j = 0; j <n; j++) {
        
    
                if (isValid(record, i, j)) {
        
                    record[i] = j;
                    res += process1(i+1, record, n);
                }
            }
            return res;
        }
    
        public static boolean isValid(int[] record, int i, int j) {
        
            for (int k = 0; k < i; k++) {
        
                // 共列 或者 共斜线
                if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
        
                    return false;
                }
            }
            return true;
        }
    
        public static int num2(int n) {
        
            if (n<1 || n>32) {
        
                return 0;
            }
            int limit = n == 32 ? -1 : (1 << n) - 1;
            return process2(limit, 0, 0, 0);
        }
    
    
        public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        
            if (colLim == limit) {
        
                return 1;
            }
    
            // 所有可以放皇后的位置 都在pos上
            // colLim | leftDiaLim | rightDiaLim   ->  总限制
            // ~（colLim | leftDiaLim | rightDiaLim） ->  左侧的一堆0干扰，右侧每个1，可尝试
            int pos = limit & ( ~(colLim | leftDiaLim | rightDiaLim) );
            int mostRightOne = 0;
            int res = 0;
            while (pos != 0) {
        
                mostRightOne = pos & (~pos +1);
                pos = pos - mostRightOne;
                res += process2(limit, colLim|mostRightOne, (leftDiaLim|mostRightOne) << 1, (rightDiaLim | mostRightOne) >>1);
    
            }
            return res;
        }
    
        public static void main(String[] args) {
        
            int n = 14;
    
            // 按位运算的N皇后
            long start = System.currentTimeMillis();
            System.out.println(num2(n));
            long end = System.currentTimeMillis();
            System.out.println("cost time: " + (end - start) + "ms");
    
            // 正常的N皇后
            start = System.currentTimeMillis();
            System.out.println(num1(n));
            end = System.currentTimeMillis();
            System.out.println("cost time: " + (end - start) + "ms");
        }
    
    }

共行不用判断，默认不共行  
判断共列 或 共斜线  
if (j == record\[k\] || Math.abs(record\[k\] - j) == Math.abs(i - k))

——————————————————————————————————————————  
当问题的基数过多时，运算时间需要很多~

可以通过 位运算 来优化

[20210406171121133.png]: /images/20221022/50ef6f7c780742be8a5284d9fa0aedb8.png