Suppose we have a solution to the nQueens problem instance i

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

Solution

solution

package com.qp.queens;

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(\"p \");
   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
p * * * *
* * p * *
* * * * p
* p * * *
* * * p *

p * * * *
* * * p *
* p * * *
* * * * p
* * p * *

* p * * *
* * * p *
p * * * *
* * p * *
* * * * p

* p * * *
* * * * p
* * p * *
p * * * *
* * * p *

* * p * *
p * * * *
* * * p *
* p * * *
* * * * p

* * p * *
* * * * p
* p * * *
* * * p *
p * * * *

* * * p *
p * * * *
* * p * *
* * * * p
* p * * *

* * * p *
* p * * *
* * * * p
* * p * *
p * * * *

* * * * p
* p * * *
* * * p *
p * * * *
* * p * *

* * * * p
* * p * *
p * * * *
* * * p *
* p * * *

enter the instance you want

6
* p * * * *
* * * p * *
* * * * * p
p * * * * *
* * p * * *
* * * * p *

* * p * * *
* * * * * p
* p * * * *
* * * * p *
p * * * * *
* * * p * *

* * * p * *
p * * * * *
* * * * p *
* p * * * *
* * * * * p
* * p * * *

* * * * p *
* * p * * *
p * * * * *
* * * * * p
* * * p * *
* p * * * *

enter the instance you want
7
p * * * * * *
* * p * * * *
* * * * p * *
* * * * * * p
* p * * * * *
* * * p * * *
* * * * * p *

p * * * * * *
* * * p * * *
* * * * * * p
* * p * * * *
* * * * * p *
* p * * * * *
* * * * p * *

p * * * * * *
* * * * p * *
* p * * * * *
* * * * * p *
* * p * * * *
* * * * * * p
* * * p * * *

p * * * * * *
* * * * * p *
* * * p * * *
* p * * * * *
* * * * * * p
* * * * p * *
* * p * * * *

* p * * * * *
* * * p * * *
p * * * * * *
* * * * * * p
* * * * p * *
* * p * * * *
* * * * * p *

* p * * * * *
* * * p * * *
* * * * * p *
p * * * * * *
* * p * * * *
* * * * p * *
* * * * * * p

* p * * * * *
* * * * p * *
p * * * * * *
* * * p * * *
* * * * * * p
* * p * * * *
* * * * * p *

* p * * * * *
* * * * p * *
* * p * * * *
p * * * * * *
* * * * * * p
* * * p * * *
* * * * * p *

* p * * * * *
* * * * p * *
* * * * * * p
* * * p * * *
p * * * * * *
* * p * * * *
* * * * * p *

* p * * * * *
* * * * * p *
* * p * * * *
* * * * * * p
* * * p * * *
p * * * * * *
* * * * p * *

* p * * * * *
* * * * * * p
* * * * p * *
* * p * * * *
p * * * * * *
* * * * * p *
* * * p * * *

* * p * * * *
p * * * * * *
* * * * * p *
* p * * * * *
* * * * p * *
* * * * * * p
* * * p * * *

* * p * * * *
p * * * * * *
* * * * * p *
* * * p * * *
* p * * * * *
* * * * * * p
* * * * p * *

* * p * * * *
* * * * p * *
* * * * * * p
* p * * * * *
* * * p * * *
* * * * * p *
p * * * * * *

* * p * * * *
* * * * * p *
* p * * * * *
* * * * p * *
p * * * * * *
* * * p * * *
* * * * * * p

* * p * * * *
* * * * * * p
* p * * * * *
* * * p * * *
* * * * * p *
p * * * * * *
* * * * p * *

* * p * * * *
* * * * * * p
* * * p * * *
p * * * * * *
* * * * p * *
* p * * * * *
* * * * * p *

* * * p * * *
p * * * * * *
* * p * * * *
* * * * * p *
* p * * * * *
* * * * * * p
* * * * p * *

* * * p * * *
p * * * * * *
* * * * p * *
* p * * * * *
* * * * * p *
* * p * * * *
* * * * * * p

* * * p * * *
* p * * * * *
* * * * * * p
* * * * p * *
* * p * * * *
p * * * * * *
* * * * * p *

* * * p * * *
* * * * * p *
p * * * * * *
* * p * * * *
* * * * p * *
* * * * * * p
* p * * * * *

* * * p * * *
* * * * * * p
* * p * * * *
* * * * * p *
* p * * * * *
* * * * p * *
p * * * * * *

* * * p * * *
* * * * * * p
* * * * p * *
* p * * * * *
* * * * * p *
p * * * * * *
* * p * * * *

* * * * p * *
p * * * * * *
* * * p * * *
* * * * * * p
* * p * * * *
* * * * * p *
* p * * * * *

* * * * p * *
p * * * * * *
* * * * * p *
* * * p * * *
* p * * * * *
* * * * * * p
* * p * * * *

* * * * p * *
* p * * * * *
* * * * * p *
* * p * * * *
* * * * * * p
* * * p * * *
p * * * * * *

* * * * p * *
* * p * * * *
p * * * * * *
* * * * * p *
* * * p * * *
* p * * * * *
* * * * * * p

* * * * p * *
* * * * * * p
* p * * * * *
* * * p * * *
* * * * * p *
p * * * * * *
* * p * * * *

* * * * p * *
* * * * * * p
* p * * * * *
* * * * * p *
* * p * * * *
p * * * * * *
* * * p * * *

* * * * * p *
p * * * * * *
* * p * * * *
* * * * p * *
* * * * * * p
* p * * * * *
* * * p * * *

* * * * * p *
* p * * * * *
* * * * p * *
p * * * * * *
* * * p * * *
* * * * * * p
* * p * * * *

* * * * * p *
* * p * * * *
p * * * * * *
* * * p * * *
* * * * * * p
* * * * p * *
* p * * * * *

* * * * * p *
* * p * * * *
* * * * p * *
* * * * * * p
p * * * * * *
* * * p * * *
* p * * * * *

* * * * * p *
* * p * * * *
* * * * * * p
* * * p * * *
p * * * * * *
* * * * p * *
* p * * * * *

* * * * * p *
* * * p * * *
* p * * * * *
* * * * * * p
* * * * p * *
* * p * * * *
p * * * * * *

* * * * * p *
* * * p * * *
* * * * * * p
p * * * * * *
* * p * * * *
* * * * p * *
* p * * * * *

* * * * * * p
* p * * * * *
* * * p * * *
* * * * * p *
p * * * * * *
* * p * * * *
* * * * p * *

* * * * * * p
* * p * * * *
* * * * * p *
* p * * * * *
* * * * p * *
p * * * * * *
* * * p * * *

* * * * * * p
* * * p * * *
p * * * * * *
* * * * p * *
* p * * * * *
* * * * * p *
* * p * * * *

* * * * * * p
* * * * p * *
* * p * * * *
p * * * * * *
* * * * * p *
* * * p * * *
* p * * * * *

if no is increasing the no of possible outcomes are increasing.so some cases it ends up with infiniteloop.no problem if no is greaterthan 4.