## Adobe Interview Question

Computer Scientists**Country:**United States

We can do this by combinations.

Observe that we have 64 * 63 possibilities for two queens, and we can change the order.

That is : 2 * 64 * 63 ways one can arrange 2 queens : T

Now, out of them, how many won't be stable?

Observe that a configuration is unstable iff The queens are in the same :

1. vertical

2. horizontal

3. diagonal.

1. Is possible by : 8 * P(8,2) ways : H

2. Is possible by : 8 * P(8,2) ways : V

3. Is possible by : 4 * ( P(8,2) + P(7,2) + ... P(2,2) ) : D

number of ways = T - H - V - D

Answer = No of ways of placing the pair of queens on the board (Y) - No of ways in which the pair intersects (X)

Y = N*N *(N*N -1)

```
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
int n = 8;
int arr[][] = new int[n][n];
long x = 0;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
x += Math.min(n-1-i, n-1-j) + Math.min(i, j) + Math.min(n-1-i,j) + Math.min(i,n-1-j);
x+= 2*n -2;
}
}
long ans = n*n * (n*n-1) - x;
System.out.println(ans);
}
```

}

```
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
int n = 8;
int arr[][] = new int[n][n];
long x = 0;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
x += Math.min(n-1-i, n-1-j) + Math.min(i, j) + Math.min(n-1-i,j) + Math.min(i,n-1-j);
x+= 2*n -2;
}
}
long ans = n*n * (n*n-1) - x;
System.out.println(ans);
}
```

}

```
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
int n = 8;
int arr[][] = new int[n][n];
long x = 0;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
x += Math.min(n-1-i, n-1-j) + Math.min(i, j) + Math.min(n-1-i,j) + Math.min(i,n-1-j);
x+= 2*n -2;
}
}
long ans = n*n * (n*n-1) - x;
System.out.println(ans);
}
```

}

```
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
int n = 8;
int arr[][] = new int[n][n];
long x = 0;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
x += Math.min(n-1-i, n-1-j) + Math.min(i, j) + Math.min(n-1-i,j) + Math.min(i,n-1-j);
x+= 2*n -2;
}
}
long ans = n*n * (n*n-1) - x;
System.out.println(ans);
}
}
```

```
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
int n = 8;
int arr[][] = new int[n][n];
long x = 0;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
x += Math.min(n-1-i, n-1-j) + Math.min(i, j) + Math.min(n-1-i,j) + Math.min(i,n-1-j);
x+= 2*n -2;
}
}
long ans = n*n * (n*n-1) - x;
System.out.println(ans);
}
```

}

Answer = No of ways of placing the pair of queens on the board (Y) - No of ways in which the pair intersects (X)

Y = N*N *(N*N -1)

- Parikh November 27, 2016