Main objective: Solve the n queens problems without recursion. You have to place n queens on an n n chessboard such that no two attack each other. Important: the chessboard should be indexed starting from 1, in standard (x, y) coordinates. Thus, (4, 3) refers to the square in the 4th column and 3rd row. We will take as input the position of many queens, and have to generate a solution with queens in this positions. (Remember, in HW1, there was only one input queen. Now, there are many.) You cannot make any recursive calls. If you make a recursive call, you will get no credit. Suggestions for coding: Use a stack. You can use any in-built stack that java provides, and can store the input chess pieces however you wish. To stress, you do not need to write your own stack. Think about the box-trace (which is the same as the stack frames) for the recursive solution for NQueens. See how your stack solution will perform the same backtracking. Its not a bad idea to start from your recursive solution for HW1, and adapt it using stacks. Format: You should provide a Makefile. On running make, it should create NQueens.jar. You should run the jar with two command line arguments: the first is an input file, the second is the output file. For example, we would call the command java -jar NQueens.jar in.txt solution.txt. The file 1 in.txt will have inputs to the main program (as described below), and the file solution.txt will have the desired solution. Each line of the input file corresponds to a different instance. Each line of the input file will have three integers: the chessboard size, the column where the input queen is placed, and the row where the input queen is placed. For example, the file may look like: 8 4 4 6 3 11 4 4 6 3 The first line means we have a 8 8 chessboard, with two queens placed at (4, 4),(6, 3). We wish to place 6 more queens without any attacking the other. The second line means we have a 1111 chessboard, with two queens placed at (4, 4),(6, 3). We wish to place 9 more queens without any attacks. So on and so forth. Output: On running the command, the following should be printed in the output file. For each line of the input file, there is a line in the output file with the placement of queens. If there is no solution to the problem, print No solution (with a newline at the end) If there is a solution, print the position of each queen as followed by the position for the next queen. The positions should be in increasing order of column, so first column first, second column second, etc. Please follow this format exactly, so that the checking script works for you. For example, the output for the input describe above could be No solution 1 2 2 8 3 10 4 4 5 9 6 3 7 5 8 7 9 11 10 1 11

this is an example input. this is the example output.

5 1 1 2 3 5 1 1 2 4 5 1 1 2 5 5 1 1 2 5 5 1 2 2 4 5 1 2 2 5 5 1 1 2 3 5 1 1 2 4 5 1 1 2 5 5 1 1 2 5 5 1 2 2 4 5 1 2 2 5