Skip to main content

N Queen problem


My favorite algorithm which includes in Recursion and backtracking method is N Queen problem.I love this problem because it helped me to solve various other problem including "Sudoku". The solution for this problem typically easy one,There are three types of attacks for the Queen to each other

This can be achieved by,if i,j are the respective coordinates which represents x = i and y = j

There are three types of attack

1. a[i] == a[j] same column or row

2. (a[i] - a[j]) - (i-j) same major diagonal

3. (a[j]-a[i]) - (j-i) same minor diagonal

The code for this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class Queens {

   /***********************************************************************
    * Return true if queen placement q[n] does not conflict with
    * other queens q[0] through q[n-1]
    ***********************************************************************/
    public static boolean isConsistent(int[] q, int n) {
        for (int i = 0; i < n; i++) {
            if (q[i] == q[n])             return false;   // same column
            if ((q[i] - q[n]) == (n - i)) return false;   // same major diagonal
            if ((q[n] - q[i]) == (n - i)) return false;   // same minor diagonal
        }
        return true;
    }

   /***********************************************************************
    * Print out N-by-N placement of queens from permutation q in ASCII.
    ***********************************************************************/
    public static void printQueens(int[] q) {
        int N = q.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (q[i] == j) System.out.print("Q ");
                else           System.out.print("* ");
            }
            System.out.println();
        }  
        System.out.println();
    }


   /***********************************************************************
    *  Try all permutations using backtracking
    ***********************************************************************/
    public static void enumerate(int N) {
        int[] a = new int[N];
        enumerate(a, 0);
    }

    public static void enumerate(int[] q, int n) {
        int N = q.length;
        if (n == N) printQueens(q);
        else {
            for (int i = 0; i < N; i++) {
                q[n] = i;
                if (isConsistent(q, n)) enumerate(q, n+1);
            }
        }
    }  


    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        enumerate(N);
    }

}

source Robert Sedgewick and Kevin Wayne N queen

Comments

Popular posts from this blog

creating first go program

for creating go program open your editor and paste this code, and save it as filename.go for example helloworld.go

package main import "fmt" func main() { fmt.Println("Hello, 世界") }
I will explain these codes in details for now , we will look how to run these code.

to run type go run helloworld.go  in terminal , we get


you can try golang online as well , golang