In an nn Latin Square, filled with n different symbols, each symbol occurs exactly once in each row and exactly once in each column. For example, the following is a Latin Square where n=3x=3:

132

213

321

Complete the implementation of the class LatinSquares that prompts the user for the value of n (you may assume 2n9) and then finds all Latin Squares using symbols 11 to n on an nn board, displays them, and reports how many there are.

// ADD NEEDED IMPORT STATEMENTS HERE public class LatinSquares { /////////////////// // INNER CLASSES // /////////////////// public static class Choice { private int numChosen; private Choice(int numChosen) { //// ADD CODE HERE //// } public static Choice firstChoice() { //// ADD CODE HERE //// } public Choice nextChoice() { //// ADD CODE HERE //// } public boolean unconsideredChoicesExist() { //// ADD CODE HERE //// } protected Choice clone() { //// ADD CODE HERE //// } public String toString() { //// ADD CODE HERE //// } } public static class StackOfChoices implements Iterable { private Choice[][] choices; //// ADD ADDITIONAL INSTANCE VARIABLES HERE //// public StackOfChoices(int n) { //// ADD CODE HERE //// } public boolean isEmpty() { //// ADD CODE HERE //// } public int size() { //// ADD CODE HERE //// } public void push(Choice choice) { //// ADD CODE HERE //// } public Choice peek() { //// ADD CODE HERE //// } public Choice pop() { //// ADD CODE HERE //// } public Iterator iterator() { //// ADD CODE HERE //// } public boolean mightHaveSolutionWith(Choice choice) { //// ADD CODE HERE //// } public String toString() { //// ADD CODE HERE //// } } //////////////////////// // INSTANCE VARIABLES // //////////////////////// private static int n = 0; private StackOfChoices stackOfChoicesMade; private Stack stackOfSolutions; public LatinSquares(int size) { LatinSquares.n = size; stackOfChoicesMade = new StackOfChoices(n); stackOfSolutions = new Stack(); } public boolean solutionFound() { //// ADD CODE HERE //// } public void solve() throws InterruptedException { Choice choice = Choice.firstChoice(); while (true) { if (stackOfChoicesMade.mightHaveSolutionWith(choice)) { stackOfChoicesMade.push(choice); choice = Choice.firstChoice(); } else if (choice.unconsideredChoicesExist()) { choice = choice.nextChoice(); } else { if (stackOfChoicesMade.isEmpty()) // Here, you intend to pop to backtrack if you can. break; // If you can't (because the stack is empty), you are done! choice = stackOfChoicesMade.pop().nextChoice(); // If the pop is safe, pick up where you // left off with your last choice. // (i.e., choose the next choice after that one) } if (solutionFound()) { reactToSolutionFound(); choice = stackOfChoicesMade.pop(); // normally we check to make sure -- but it's safe to pop.. why? choice = choice.nextChoice(); // keep going to try to find other solutions } } } public void reactToSolutionFound() { //// ADD CODE HERE //// } public static void main(String[] args) throws InterruptedException { System.out.println("Enter n: "); Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); scanner.close(); LatinSquares latinSquares = new LatinSquares(n); latinSquares.solve(); System.out.println(" Solutions: "); for (String solution : latinSquares.stackOfSolutions) { System.out.println(solution); } System.out.println(latinSquares.stackOfSolutions.size() + " solutions found! "); } }