Question

9. Suppose we have a solution to the n-Queens problem instance in which n 4. Can we extend this solution to find a solution to the problem instance in which n 5? Can we then use the solutions for n 4 and n 5 to construct a solution to the instance in which n 6 and continue this dynamic programming approach to find a solution to any instance in which n 4? Justify your answer.

Answer 1

n-Queens Problems:

import java.util.Scanner;

public class QueensProblem {

  
   public static void possibleChoices(int k) {
   int[] choices = new int[k];
   possibleChoices (choices, 0);
   }

   public static void possibleChoices(int[] queen, int no) {
   int n = queen.length;
   if (no == n) display(queen);
   else {
   for (int i = 0; i < n; i++) {
   queen[no] = i;
   if (isConsistentApproach(queen, no)) possibleChoices(queen, no+1);
   }
   }
}

   public static void display(int[] queen) {
   int z = queen.length;
   for (int k = 0; k < z; k++) {
   for (int j = 0; j < z; j++) {
   if (queen[k] == j) System.out.print("x ");
   else System.out.print("* ");
   }
   System.out.println();
   }
   System.out.println();
   }

   public static boolean isConsistentApproach(int[] queen, int no) {
   for (int k = 0; k < no; k++) {
   if (queen[k] == queen[no]) return false; // same column
   if ((queen[k] - queen[no]) == (no - k)) return false; // same major diagonal
   if ((queen[no] - queen[k]) == (no - k)) return false; // same minor diagonal
   }
   return true;
   }
       public static void main(String... arguments) {
          
           Scanner scan=new Scanner(System.in);
           System.out.println("enter the instance you want");
           int choice=scan.nextInt();
          
           QueensProblem.possibleChoices(choice);
}

   }

output:

enter the instance you want
5
x * * * *
* * x * *
* * * * x
* x * * *
* * * x *

x * * * *
* * * x *
* x * * *
* * * * x
* * x * *

* x * * *
* * * x *
x * * * *
* * x * *
* * * * x

* x * * *
* * * * x
* * x * *
x * * * *
* * * x *

* * x * *
x * * * *
* * * x *
* x * * *
* * * * x

* * x * *
* * * * x
* x * * *
* * * x *
x * * * *

* * * x *
x * * * *
* * x * *
* * * * x
* x * * *

* * * x *
* x * * *
* * * * x
* * x * *
x * * * *

* * * * x
* x * * *
* * * x *
x * * * *
* * x * *

* * * * x
* * x * *
x * * * *
* * * x *
* x * * *

enter the instance you want

6
* x * * * *
* * * x * *
* * * * * x
x * * * * *
* * x * * *
* * * * x *

* * x * * *
* * * * * x
* x * * * *
* * * * x *
x * * * * *
* * * x * *

* * * x * *
x * * * * *
* * * * x *
* x * * * *
* * * * * x
* * x * * *

* * * * x *
* * x * * *
x * * * * *
* * * * * x
* * * x * *
* x * * * *

enter the instance you want
7
x * * * * * *
* * x * * * *
* * * * x * *
* * * * * * x
* x * * * * *
* * * x * * *
* * * * * x *

x * * * * * *
* * * x * * *
* * * * * * x
* * x * * * *
* * * * * x *
* x * * * * *
* * * * x * *

x * * * * * *
* * * * x * *
* x * * * * *
* * * * * x *
* * x * * * *
* * * * * * x
* * * x * * *

x * * * * * *
* * * * * x *
* * * x * * *
* x * * * * *
* * * * * * x
* * * * x * *
* * x * * * *

* x * * * * *
* * * x * * *
x * * * * * *
* * * * * * x
* * * * x * *
* * x * * * *
* * * * * x *

* x * * * * *
* * * x * * *
* * * * * x *
x * * * * * *
* * x * * * *
* * * * x * *
* * * * * * x

* x * * * * *
* * * * x * *
x * * * * * *
* * * x * * *
* * * * * * x
* * x * * * *
* * * * * x *

* x * * * * *
* * * * x * *
* * x * * * *
x * * * * * *
* * * * * * x
* * * x * * *
* * * * * x *

* x * * * * *
* * * * x * *
* * * * * * x
* * * x * * *
x * * * * * *
* * x * * * *
* * * * * x *

* x * * * * *
* * * * * x *
* * x * * * *
* * * * * * x
* * * x * * *
x * * * * * *
* * * * x * *

* x * * * * *
* * * * * * x
* * * * x * *
* * x * * * *
x * * * * * *
* * * * * x *
* * * x * * *

* * x * * * *
x * * * * * *
* * * * * x *
* x * * * * *
* * * * x * *
* * * * * * x
* * * x * * *

* * x * * * *
x * * * * * *
* * * * * x *
* * * x * * *
* x * * * * *
* * * * * * x
* * * * x * *

* * x * * * *
* * * * x * *
* * * * * * x
* x * * * * *
* * * x * * *
* * * * * x *
x * * * * * *

* * x * * * *
* * * * * x *
* x * * * * *
* * * * x * *
x * * * * * *
* * * x * * *
* * * * * * x

* * x * * * *
* * * * * * xx
* x * * * * *
* * * x * * *
* * * * * x *
x * * * * * *
* * * * x * *

* * x * * * *
* * * * * * x
* * * x * * *
x * * * * * *
* * * * x * *
* x * * * * *
* * * * * x *

* * * x * * *
x * * * * * *
* * x * * * *
* * * * * x *
* x * * * * *
* * * * * * x
* * * * x * *

* * * x * * *
x * * * * * *
* * * * x * *
* x * * * * *
* * * * * x *
* * x * * * *
* * * * * * x

* * * x * * *
* x * * * * *
* * * * * * x
* * * * x * *
* * x * * * *
x * * * * * *
* * * * * x *

* * * x * * *
* * * * * x *
x * * * * * *
* * x * * * *
* * * * x * *
* * * * * * x
* x * * * * *

* * * x * * *
* * * * * * x
* * x * * * *
* * * * * x *
* x * * * * *
* * * * x * *
x * * * * * *

* * * x * * *
* * * * * * x
* * * * x * *
* x * * * * *
* * * * * x *
x * * * * * *
* * x * * * *

* * * * x * *
x * * * * * *
* * * x * * *
* * * * * * x
* * x * * * *
* * * * * x *
* x * * * * *

* * * * x * *
x * * * * * *
* * * * * x *
* * * x * * *
* x * * * * *
* * * * * * x
* * x * * * *

* * * * x * *
* x * * * * *
* * * * * x *
* * x * * * *
* * * * * * x
* * * x * * *
x * * * * * *

* * * * x * *
* * x * * * *
x * * * * * *
* * * * * x *
* * * x * * *
* x * * * * *
* * * * * * x

* * * * x * *
* * * * * * x
* x * * * * *
* * * x * * *
* * * * * x *
x * * * * * *
* * x * * * *

* * * * x * *
* * * * * * x
* x * * * * *
* * * * * x *
* * x * * * *
x * * * * * *
* * * x * * *

* * * * * x *
x * * * * * *
* * x * * * *
* * * * x * *
* * * * * * x
* x * * * * *
* * * x * * *

* * * * * x *
* x * * * * *
* * * * x * *
x * * * * * *
* * * x * * *
* * * * * * x
* * x * * * *

* * * * * x *
* * x * * * *
x * * * * * *
* * * x * * *
* * * * * * x
* * * * x * *
* x * * * * *

* * * * * x *
* * x * * * *
* * * * x * *
* * * * * * x
x * * * * * *
* * * x * * *
* x * * * * *

* * * * * x *
* * x * * * *
* * * * * * x
* * * x * * *
x * * * * * *
* * * * x * *
* x * * * * *

* * * * * x *
* * * x * * *
* x * * * * *
* * * * * * x
* * * * x * *
* * x * * * *
x * * * * * *

* * * * * x *
* * * x * * *
* * * * * * x
x * * * * * *
* * x * * * *
* * * * x * *
* x * * * * *

* * * * * * x
* x * * * * *
* * * x * * *
* * * * * x *
x * * * * * *
* * x * * * *
* * * * x * *

* * * * * * x
* * x * * * *
* * * * * x *
* x * * * * *
* * * * x * *
x * * * * * *
* * * x * * *

* * * * * * x
* * * x * * *
x * * * * * *
* * * * x * *
* x * * * * *
* * * * * x *
* * x * * * *

* * * * * * x
* * * * x * *
* * x * * * *
x * * * * * *
* * * * * x *
* * * x * * *
* x * * * * *