java - 8クイーン問題

Question

8/4 クイーンの問題を実装するにはどうすればよいですか?DFS/BFS を使用する必要がありますか?DF の方が優れていると思います。誰でもいくつかの疑似コード/ガイドラインを与えることができますか?

Answer 1

スタックとバックトラッキングを使用します。最も簡単な方法は再帰です。

これらの他の SO 投稿を参照してください。

C ++でのダム8クイーン問題

Answer 2

私のソリューションには 2 つの事前定義されたロジックがあり、行にはクイーンが 1 つだけあり、列にはクイーンが 1 つしかありません。長さが 8 の 1 次元配列があります。すべての配列値は 0 ～ 7 のいずれかに設定されますが、すべての値は 1 回だけ使用されます (0 ～ 7 の値の順列) arr[0]=5 値は列のクイーンを意味します最初の行の 6 arr[1]=3 の値は、2 行目の列 4 のクイーンを意味します。配列チェックで交差違反値を制御するだけで、行または行の違反をチェックする必要はありません。順列およびクロス違反関数がすべて必要です (C++ STL には順列関数があり、違反関数をクロスするだけで済みます)。

Answer 3

Here is my implementation using backtracking. Change the value of N to get the different solutions.

It will print all the solutions available for given number of queens.

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;
    }
}

Answer 4

クイーンが (i,j) および (k,l) 座標にある場合、次の場合に互いに攻撃できます。

1. i=k (同行)
2. j=l (同列)

3. |ik|=|jl| (斜め),| | | は絶対値を示します

   bool place(k,i)
   {
   //returns true if the queen can be placed at k-th row and i-th column
   //x[] is a global array with first (k-1) values set already.
   //x[p]=q means a queen is at location (p,q)
   
   for(j=1 to k-1)
   {
   if(x[j]==i)||(ABS(x[j]-i)==ABS(j-k))  //checking if another queen in same column or     diagonally
   return false;
   }
   return true;
   }
   

   バックトラッキングを使用してすべての可能な配置を印刷するには:

   ボイド NQueens(k,n) {

   for(i=1 to n)
   {
   if(place(k,i)) //checking if queen can be placed at (k,i)
   {
   x[k]=i;
   if(k==n) then write (x[1:n]);  
   else Nqueens(k+1,n);
    }
    }
   }
   

※ソーラブスクールより引用