9/05/2014

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

installing perl dancer in ubuntu

For installing perl dancer you need curl utility for installing curl ,   sudo apt-get install curl Now we can install Perl-Dancer by thi...