$ mkdir ~/cs170/labs/lab32 $ cd ~/cs170/labs/lab32
On Wednesday, we spent a fair amount of time handtracing the N-Queens problem. As a result, we hopefully have a better understanding of how the process of backtracking works. However, the N-Queens solver you hand traced stopped as soon as it had one solution. There's MANY solutions for that problem. What do we need to change to get it to find all of the solutions?
Download the file perms.cc. This file houses the main driver program for a C++ program that prints all of the permutations of a list of unique integers. Your job is to complete this program.
There's only one required function to
write: void outputPermutations(LinkedList *
permutationElements). This function, when called, should
result in every permutation of the provided linked list being output
to the terminal.
You WILL need at least one helper function! Think about how you are going to modify the permutationElements list to make progressing to your base case easier. Would an additional list be worth having?
How many elements? 4 [0, 1, 2, 3] [0, 1, 3, 2] [0, 2, 1, 3] [0, 2, 3, 1] [0, 3, 1, 2] [0, 3, 2, 1] [1, 0, 2, 3] [1, 0, 3, 2] [1, 2, 0, 3] [1, 2, 3, 0] [1, 3, 0, 2] [1, 3, 2, 0] [2, 0, 1, 3] [2, 0, 3, 1] [2, 1, 0, 3] [2, 1, 3, 0] [2, 3, 0, 1] [2, 3, 1, 0] [3, 0, 1, 2] [3, 0, 2, 1] [3, 1, 0, 2] [3, 1, 2, 0] [3, 2, 0, 1] [3, 2, 1, 0]
The solution you described above probably only works for a list of unique elements. It will not work if there are any duplicates in the list.
In order to more easily work for non-unqiue elements, we need to
modify the linked list: Add a new method int pop(int index)
which behaves like pop for lists in python. It should
remove (and return!) the value at the specified position in the list.
Once this is written, rewrite your backtracking solution to utilize this new functionality.