8皇后问题

Question

我该如何实现八皇后问题？我应该使用深度优先搜索（DFS）还是广度优先搜索（BFS），我认为DFS会更好。有人能给一些伪代码/指导吗？

- akshay

---

是啊，赋值操作万岁！完成作业的最佳方式就是自己动手去做。 - Ilya Saunkin

如果你想找到八皇后问题的所有解决方案，BFS可能会很有趣。如果你想尽快找到任何一个解决方案，DFS是正确的选择。 - Andreas Dolk

Answer 1

使用堆栈和回溯法，最简单的方法是通过递归实现。

参考以下其他stackoverflow帖子： C++中的愚蠢八皇后问题

- Robert S. Barnes

---

那里已经有一个实现了，既然你已经有一个可行的解决方案，还需要它做什么呢？ - Ilya Saunkin

Answer 2

如果皇后位于(i,j)和(k,l)坐标，则它们可以互相攻击。

1. i=k（同一行）
2. j=l（同一列）

3. |i-k|=|j-l|（对角线），| | 表示绝对值

   bool place(k,i)
   {
   //如果皇后可以放在第k行和第i列，则返回true
   //x[]是一个全局数组，前(k-1)个值已经设置好了。
   //x[p]=q表示皇后位于位置(p,q)
   
   for(j=1 to k-1)
   {
   if(x[j]==i)||(ABS(x[j]-i)==ABS(j-k))  //检查是否有另一个皇后在同一列或对角线上
   return false;
   }
   return true;
   }
   

   使用回溯打印所有可能的摆法：

   void NQueens(k,n) {

   for(i=1 to n)
   {
   if(place(k,i)) //检查皇后是否可以放在(k,i)处
   {
   x[k]=i;
   if(k==n) then write (x[1:n]);  
   else Nqueens(k+1,n);
    }
    }
   }
   

*参考自Saurabh学校

- Shivam Verma

Answer 3

我的解决方案有两个预定义逻辑，一行只有一个皇后，一列也只有一个皇后。 有一个长度为8的一维数组。所有数组值都设置为0-7中的一个，但所有值仅使用一次（0-7的排列）。 arr [0] = 5的值表示第一行第6列有皇后 arr [1] = 3的值表示第二行第4列有皇后， 只需检查数组上的交叉违规值，无需检查行或列违规。排列和交叉违规函数是您所需要的全部内容（C ++ STL具有排列函数，只需要交叉违规函数）。

- Erdinç Taşkın

Answer 4

这是我的回溯法实现。 改变N的值可以获得不同的解决方案。

它将打印出给定皇后数量的所有可用解决方案。

package com.org.ds.problems;

public class NQueueProblem {
private static int totalSolution = 0;
    public static void main(String[] args) {
        int n = 5;
        int arr[][] = new int[n][n];
        backTrack(arr, 0);
        System.out.println("\nTotal Number of Solutions are:- " + totalSolution);
    }

    private static void printQueuens(int[][] arr) {
        totalSolution++;
        System.out.println("\n========Start Printing Solution "+totalSolution+"=========");
        for(int i=0; i<arr.length;i++) {
            for(int j=0; j<arr.length;j++) {
                if(arr[i][j] == 1)
                    System.out.print(" Q"+(i+1) + " |");
                else
                    System.out.print("    |");
            }
            System.out.println();
        }
    }

    private static boolean backTrack(int[][] arr, int row) {
        if (row < 0 || row >= arr.length)
            return true;

        for (int col = 0; col < arr.length; col++) {
            if (isAttacked(arr, row, col)) {
                arr[row][col] = 1;
                if (backTrack(arr, row + 1)) {
                    if(row == (arr.length-1)) {
                        printQueuens(arr);
                        arr[row][col] = 0;
                    }
                    else {
                        return true;    
                    }
                } else {
                    arr[row][col] = 0;
                }
            }
        }
        return false;
    }

    private static boolean isAttacked(int[][] arr, int row, int col) {
        if (row == 0)
            return true;
        // check for same row
        for (int i = 0; i < arr.length; i++) {
            if (arr[row][i] == 1)
                return false;
        }
        // check for same col
        for (int i = 0; i <= row; i++) {
            if (arr[i][col] == 1)
                return false;
        }
        // check for diagonal
        // a.) Left dia
        int i = row - 1;
        int j = col - 1;
        while (i >= 0 && j >= 0) {
            if (arr[i][j] == 1)
                return false;
            i--;
            j--;
        }
        // b.) right dia
        i = row - 1;
        j = col + 1;
        while (i >= 0 && j < arr.length) {
            if (arr[i][j] == 1)
                return false;
            i--;
            j++;
        }
        return true;
    }
}

- Pramendra Raghuwanshi