Use recursive backtracking to solve a simple puzzle-type problem in which you have to assign values from a given list of numbers to each index in an array. The values you assign must follow the rule that to be assigned as thenth item in the array, the value must be a multiple ofn. For example, the first item (index 0) must be a multiple of 1, the second item (index 1) must be a multiple of 2, the third item a multiple of 3, and so on. For this task, you will need to write some additional helper methods. For the purpose of testing, all methods should be public.

Objectives

• Practice creating a class
• Writing helper methods for a larger task
• Using recursive backtracking to solve a problem

Steps

2. Start Intellij
4. At the Welcome Window click Create New Project

1. In the New Project window
   1. Type the name of the project in theProject name: textbox.
      1. Name your projectBacktracking

1. Download the starter code (Multiples.java) from Mimir and save it in the src directory of your new project.

2. Add a method namedisMultiple which takes two integer parameters,num anddiv. It should returntrue ifnum is a multiple ofdiv, andfalse otherwise. The mod operator (%) will likely be helpful in writing this method.
4. Add a method namedassignValue which takes two integer parameters,n andi. It should get the value at indexi fromnumbers, and assign it to indexn inresult. It should then remove the value at indexi fromnumbers. This will allow your program to only use a number once when finding a solution to the problem.
6. Add a method namedunassignValue which takes a single integer parameter,n. It should add the value at indexn fromresults back intonumbers (at index0.) Then it should assign0 to indexn inresult to clear out the value from the results. This will allow your program to "undo" a choice it made when it needs to backtrack and try other possibilities.
8. Finally, you must now work on the recursive backtracking methodsolve( int n ).
   2. First, add a base case to the method. Because it will start at index 0 and assign values before moving on to the next index, the method will assume that any index beforen has already been given a value in a previous call to the method. So your base case will be whenn is past the last valid index forresult, and should returntrue to indicate that the problem was solved.
   4. Next, you need to handle the recursive case.For each number innumbers, the method should check if that number is valid for indexn (meaning it is a multiple ofn+1). If it is valid, then it should assign that value at index n. Then recursively call the method to solve the rest of the problem, but make sure to store the return value of that recursive call in aboolean variable. If the recursive call returnedtrue, this means the rest of the problem was solved by the recursive call, and no more solving is needed (the method can returntrue.) For now, have the method returnfalse if the recursive call returnedfalse.If you run or submit your code at this point, you will see that it solves the problems which don't require backtracking.
   6. To allow backtracking, we need the method not to quit when a single recursive call fails, so delete the part of the code that returnsfalse when the recursive call returnedfalse. Instead, what it should do is un-assign the value atn when the recursive call failed to find a solution (to undo the choice of value, because we found there was no solution possible with that choice of value.) The method should returnfalse only if the for loop finishes without finding a solution, so returnfalse outside the for loop (nowhere else!)If you run or submit your code at this point, it should solve the problems which do require backtracking and correctly report when no solution is possible.

Set a breakpoint in IntelliJ at the line insolve() wheresolve(0) is called. Run in debug mode. Step through the code (step intosolve(0) and then use step over from then onward) and watch as it solves each of the problems (or discovers no solution is possible. This will give you a clearer idea of how the recursion finds solutions and how the backtracking allows it to try other options when it fails to find a solution.

Below is the code I have completed so far but I am not exactly sure how to use recursion and backtracking to solve the rest of this problem.

import java.util.ArrayList; import java.util.Arrays; public class Multiples { private int[] result; private ArrayList numbers; public Multiples( ArrayList numbers ) { this.numbers = numbers; this.result = new int[numbers.size()]; } // HELPER METHODS GO HERE public boolean isMultiple(int num, int div) { return num % div == 0; } public void assignValue(int n, int i) { result[n] = numbers.get(i); numbers.remove(i); } public void unassignValue(int n) { numbers.add(0, result[n]); result[n] = 0; } /** * DO NOT CHANGE! * Method to begin solving the problem for the first index in results. * * @return True if solution was found, false if none was possible. */ public boolean solve() { return solve(0); } /** * Recursive method to solve the problem from a given index onward. Assumes * that any index before n was already assigned a valid value. * * @param n The current index in the results array to find a value for. * @return True if solution was found, false if none was possible from this index. */ private boolean solve(int n) { if (n > result.length) { return true; } if (isMultiple(n,n + 1)) { assignValue(n, n); solve(n + 1); } unassignValue(n); } public int[] getResult() { return result; } public ArrayList getNumbers() { return numbers; } public static void main(String[] args) { Integer[] numbers; Multiples m; //FIRST TEST (SOLUTION POSSIBLE WITHOUT BACKTRACKING) numbers = new Integer[]{1, 6, 21, 40, 25}; m = new Multiples(new ArrayList(Arrays.asList(numbers))); if (m.solve()) { System.out.println("Found solution for " + Arrays.toString(numbers)); } else { System.out.println("No solution possible!"); } System.out.println(Arrays.toString(m.getResult())); System.out.println(); //SECOND TEST (SOLUTION POSSIBLE WITH BACKTRACKING) numbers = new Integer[]{15, 10, 6, 12, 16}; m = new Multiples(new ArrayList(Arrays.asList(numbers))); if (m.solve()) { System.out.println("Found solution for " + Arrays.toString(numbers)); } else { System.out.println("No solution possible!"); } System.out.println(Arrays.toString(m.getResult())); System.out.println(); //THIRD TEST (NO SOLUTION) numbers = new Integer[]{15, 10, 6, 12, 17}; m = new Multiples(new ArrayList(Arrays.asList(numbers))); if (m.solve()) { System.out.println("Found solution for " + Arrays.toString(numbers)); } else { System.out.println("No solution possible!"); } System.out.println(Arrays.toString(m.getResult())); } }