Motivation In this assignment, you will use backtracking to find normal semi-magic squares. A magic square is a n n square grid of positive integers with special properties. In particular, each cell must contain a unique integer (no duplicates), and the sum of the integers in any row, column, or diagonal is equal to a particular value (called the magic sum). For instance, consider the following 3 3 magic square, with magic sum of 72:

23 28 21

22 24 26

27 20 25

A semi-magic square is similar to a magic square, except only the rows and columns are considered (the sum of the diagonals is not constrained). All magic squares are also semi-magic squares, but not all semi-magic squares are magic squares.

Finally, a normal magic square contains each of the first n^2 positive integers. A normal magic square (or semi-magic square) always has a magic sum of n(n^2 + 1)/2. For instance,consider the following 33 normal magic square, with magic sum of 3(3^2 + 1)/2 = 15:

8 1 6

3 5 7

4 9 2

Note that, as a normal semi-magic square, this square contains each value from 1 to 3^2 = 9.

In this assignment, we will focus on n n normal semi-magic squares, containing values 1 to n^2, where each row and column must add up to n(n^2 + 1)/2.

2 Provided files First, carefully read the provided files.

2.1 Provided code

The Queens class includes a backtracking solution to the 8 Queens problem. If you run this class with the -t command line argument (called a flag), it will run tests of its reject, isFullSolution, extend, next methods.

The SemiMagic class includes the basic skeleton of a backtracking solution. This class also includes the method readSquare, which reads a partially-completed square from a file and returns it as a two-dimensional int array, with 0 designating an empty cell (yet to be filled). Finally, it includes a method printSquare, which prints out a square to the terminal.

It is recommended that you use this provided code as a starting point. However, you may choose not to use this provided code, as long as your program reads the same input format and uses the required backtracking techniques.

2.2 Example Squares

Several partially-completed squares are available for you to test your code in the squares/directory. Below is a summary of these files.

Filename Size Solvable?

two.sq

2 2

Solveable - No

three1.sq

3 3

Solveable - Yes

three2.sq

3 3

Solveable - No

five1.sq

5 5

Solveable - Yes

five2.sq

5 5

Solveable - No

Each of these files is plaintext (i.e., can be opened with a text editor such as Notepad or TextEdit). Columns are separated by tabs, and rows are separated by newline. You can also use this format to create partially-completed squares of your own for testing.

3 Tasks

You must write a backtracking program to find values for all of the cells in the square that are not filled. Your solution must satisfy the rules of normal semi-magic squares: each number between 1 and n^2 must appear exactly once, and each row and column must sum up to n(n^2 + 1)/2. You must accomplish this using the backtracking techniques discussed and demonstrated in lecture and in Queens.java. That is, you need to build up a solution recursively, one cell at a time, until you determine that the current square is impossible to complete (in which case you will backtrack and try another assignment), or that the current square is complete and valid. Alternately, if you conclude that there is no valid solution for the problem instance given, you should print a message indicating as such.

Your class must be named SemiMagic, and therefore must be in a file with the name SemiMagic.java. It must also be in the package cs.a3.

3.1 Modes

Your program must support three modes. In blank mode, you will start from a blank square, and construct a normal semi-magic square of the requested size. In fill mode, you will start from a partially-completed square read from a file. Finally, in test mode, you will print the results of several tests of the backtracking mechanics.

Blank mode To execute in blank mode, simply give the square size as a command-line argument. For instance, the following command should find a 3 3 normal semi-magic square, starting from a blank square.

java cs.a3.SemiMagic 3

Note: Blank mode can be very time-consuming for larger sizes. Your code should be able to solve up to 4 4 in blank mode within a reasonable time limit (it is okay if 5 5 takes too long).

Fill mode

To execute in fill mode, give the square size and square filename as command- line arguments. The following command will find a 4 4 normal semi-magic square, starting from the provided partially-completed square described in square.sq (in the format described in section 2.2).

java cs.a3.SemiMagic 4

square.sq

Your program will read in the partially-filled square from the file. This square will have several cells filled, and other cells (value of 0) will be considered empty. Your goal is to find values for the remaining cells without changing any of the cells provided (i.e., you can change only those with an initial value of 0).

Note that specifying a filename with all 0 values should behave identically to blank mode. Also note that filenames are relative to your terminal location, so square files should stay outside of the package directory (and if they are inside the squares directory, you should specify them as, e.g., squares/two.sq).

Test mode

When run with the argument -t, your program should execute in test mode. In this mode, you should run each of the test methods described below in section 3.3. An example command is given below.

java cs.a3.SemiMagic -t

3.2 Required Methods

As stated above, you must use the techniques we discussed in lecture for recursive back-tracking. As such, you will then need to write the following methods to support your backtracking algorithm.

isFullSolution, a method that accepts a partial solution and returns true if it is a complete,valid solution.

reject, a method that accepts a partial solution and returns true if it should be rejected because it can never be extended into a complete solution.

extend, a method that accepts a partial solution and returns another partial solution that includes one additional choice added on. This method will return null if no more choices can be added to the solution.

Note: Be sure that your extend method creates a new partial solution, rather than modifying its argument in-place (recall that the runtime stack can only contain references, not objects themselves!).

next, a method that accepts a partial solution and returns another partial solution in which the most recent choice that was added has been changed to its next option. This method will return null if there are no more options for the most recent choice that was made (even if there are other options for other choices!).

Hints:

1. You should implement the above methods as efficiently as possible.

6 bonus points will be given for solutions efficient enough to solve a very hard puzzle within a fixed time limit. At a minimum, you should be able to solve the examples provided within 1 minute.

2. One key challenge in this assignment is, in fill mode, differentiating between cells that were filled by your program (and thus can be changed) and those that were specified in the provided file (and thus cannot be changed). If you were solving this puzzle by hand on paper, how would you differentiate between these two types of cells? I can think of two main approaches, each of which has a programming analogue.

3. As with the examples discussed in class, none of the 4 methods described above needs to be recursive itself. The recursion happens within solve, enabled by these helper methods.

3.3 Test Methods

When developing a complex program such as this one, it is important to test your progress as you go. For this reason, in addition to the backtracking-supporting methods above, you will be required to test your methods as you develop them. Re-read starting at Chapter 2.16 to review the concepts behind writing test methods. To test each of the backtracking methods, you need to write the following test methods. For each one, you should create a variety of partial solutions that cover as many corner cases as you can think of. Then, call the method you are testing on each partial solution, and ensure that the result is as expected. Include enough test cases that the correct output convinces you that your method works properly in all situations.

testIsFullSolution, a method that generates partial solutions and ensures that the isFullSolution method correctly determines whether each is a complete solution.

testReject, a method that generates partial solutions and ensures that the reject method correctly determines whether each should be rejected.

testExtend, a method that generates partial solutions and ensures that the extend method correctly extends each with the correct next choice.

testNext, a method that generates partial solutions and ensures that the, in each, next method correctly changes the most recent choice that was added to its next option. You may either hardcode your test partial solutions, or submit .sq files containing the squares you want to test. In either case, when your program is run with the -t flag, your program must run the above four test methods and output the results.

4 Grading

Your grade for this assignment will be based on:

Your programs success at finding magic squares in blank mode (20%) and fill mode (40%). This includes correctly stating that there is no solution, where applicable.

The thoroughness of your test methods (40%).

All programs will be tested on the command line, so if you use an IDE to develop your program, you must export the java files from the IDE and ensure that they compile and run on the command line. Do not submit the IDEs project files.

Specifically, javac cs/a3/SemiMagic.java must compile your program, when executed from the root of your cs-a3-abc123 directory. Similarly, the commands given in section 3.1 should run your program, when executed from the root of your directory. In addition to your code, you may wish to include a README.txt file that describes features of your program that are not working as expected, to assist the TA in grading the portions that do work as expected

Provided Code:

Queens.java

import java.util.Arrays; public class Queens { /** * Checks if a partial solution is a complete and valid solution. * @param partial The partial solution * @return true if the partial solution is complete and valid, false otherwise. */ public static boolean isFullSolution(int[] partial) { // Check that all queens were placed for (int i = 7; i >= 0; i--) { if (partial[i] == 0) { return false; } } // The solution is known to be complete, check if it is valid if (reject(partial)) { return false; } // The solution is complete and valid return true; } /** * Checks if a partial solution should be rejected because it can never be extended to a * complete solution. * @param partial The partial solution * @return true if the partial solution should be rejected, false otherwise. */ public static boolean reject(int[] partial) { // Check every pair of queens to see if they are in conflict for (int i = 0; i < 8; i++) { for (int j = 0; j < i; j++) { if (partial[i] == 0 || partial[j] == 0) { // One of these queens is not placed, so they cannot be in conflict } else if (i != j && partial[i] == partial[j]) { // These queens are in the same row return true; } else if (partial[j] - partial[i] == j - i) { // These queens are in the same positive diagonal return true; } else if (partial[j] - partial[i] == i - j) { // These queens are in the same negative diagonal return true; } } } // No pair of queens was in conflict, so we should not reject return false; } /** * Extends a partial solution by adding one additional queen. * @param partial The partial solution * @return a partial solution with one more queen added, or null if no queen can be added. */ public static int[] extend(int[] partial) { // Initialize the new partial solution int[] temp = new int[8]; for (int i = 0; i < 8; i++) { if (partial[i] != 0) { // Copy each queen that has been placed temp[i] = partial[i]; } else { // Add a queen in row 1 of the first empty column temp[i] = 1; return temp; } } // If we reached this point, all queens were already placed, so we cannot extend. Return // null. return null; } /** * Moves the most recently-placed queen to its next possible position. * @param partial The partial solution * @return a partial solution with the most recently-placed queen moved to its next possible * position, or null if we are out of options for the most recent queen. */ public static int[] next(int[] partial) { int[] temp = new int[8]; int i = 0; while (i < 8) { if (i == 7 || partial[i+1] == 0) { // The most recent queen is the one in the last column, or the last one in a // non-empty column if (partial[i] >= 8) { // The queen is at the top, so we cannot try anything else return null; } else { // Move the queen up one row temp[i] = partial[i] + 1; break; } } else { // This isn't the last queen, so just copy it temp[i] = partial[i]; } i++; } return temp; } /** * Tests the isFullSolution method using several partial solutions. */ public static void testIsFullSolution() { int[][] fullSolutions = new int[][] { {2, 4, 6, 8, 3, 1, 7, 5}, {1, 7, 4, 6, 8, 2, 5, 3}, }; int[][] notFullSolutions = new int[][] { {0, 0, 0, 0, 0, 0, 0, 0}, {2, 4, 6, 8, 3, 5, 7, 0}, {0, 2, 0, 0, 2, 0, 0, 0}, {0, 2, 0, 0, 1, 0, 0, 2}, {2, 4, 6, 8, 3, 1, 5, 0}, {0, 5, 0, 0, 2, 0, 0, 0}, {1, 7, 4, 6, 8, 2, 5, 2}, {1, 3, 5, 7, 2, 4, 6, 8}, }; System.err.println("These should be full:"); for (int[] test : fullSolutions) { if (isFullSolution(test)) { System.err.println("\tFull sol'n:\t" + Arrays.toString(test)); } else { System.err.println("\tNot full sol'n:\t" + Arrays.toString(test)); } } System.err.println("These should NOT be full:"); for (int[] test : notFullSolutions) { if (isFullSolution(test)) { System.err.println("\tFull sol'n:\t" + Arrays.toString(test)); } else { System.err.println("\tNot full sol'n:\t" + Arrays.toString(test)); } } } /** * Tests the reject method using several partial solutions. */ public static void testReject() { int[][] notRejected = new int[][] { {0, 0, 0, 0, 0, 0, 0, 0}, {2, 4, 6, 8, 3, 5, 7, 0}, {2, 4, 6, 8, 3, 1, 7, 5}, }; int[][] rejected = new int[][] { {0, 2, 0, 0, 2, 0, 0, 0}, {0, 2, 0, 0, 1, 0, 0, 2}, {2, 4, 6, 8, 3, 1, 5, 0}, {0, 5, 0, 0, 2, 0, 0, 0}, }; System.err.println("These should NOT be rejected:"); for (int[] test : notRejected) { if (reject(test)) { System.err.println("\tRejected:\t" + Arrays.toString(test)); } else { System.err.println("\tNot rejected:\t" + Arrays.toString(test)); } } System.err.println("These should be rejected:"); for (int[] test : rejected) { if (reject(test)) { System.err.println("\tRejected:\t" + Arrays.toString(test)); } else { System.err.println("\tNot rejected:\t" + Arrays.toString(test)); } } } /** * Tests the extend method using several partial solutions. */ public static void testExtend() { int[][] noExtend = new int[][] { {2, 4, 6, 8, 3, 1, 7, 5}, {1, 7, 4, 6, 8, 2, 5, 3}, {1, 7, 4, 6, 8, 2, 5, 2}, {1, 3, 5, 7, 2, 4, 6, 8}, }; int[][] extend = new int[][] { {0, 0, 0, 0, 0, 0, 0, 0}, {2, 4, 6, 8, 3, 5, 7, 0}, {2, 4, 6, 8, 0, 0, 0, 0}, {2, 4, 6, 8, 3, 1, 5, 0}, }; System.err.println("These can NOT be extended:"); for (int[] test : noExtend) { System.err.println("\tExtended " + Arrays.toString(test) + " to " + Arrays.toString(extend(test))); } System.err.println("These can be extended:"); for (int[] test : extend) { System.err.println("\tExtended " + Arrays.toString(test) + " to " + Arrays.toString(extend(test))); } } /** * Tests the next method using several partial solutions. */ public static void testNext() { int[][] noNext = new int[][] { {1, 3, 5, 7, 2, 4, 6, 8}, {2, 4, 6, 8, 0, 0, 0, 0}, }; int[][] next = new int[][] { {2, 4, 6, 8, 3, 1, 7, 5}, {1, 7, 4, 6, 8, 2, 5, 3}, {1, 7, 4, 6, 8, 2, 5, 2}, {1, 0, 0, 0, 0, 0, 0, 0}, {2, 4, 6, 8, 3, 5, 7, 0}, {2, 4, 6, 8, 3, 1, 5, 0}, }; System.err.println("These can NOT be next'd:"); for (int[] test : noNext) { System.err.println("\tNexted " + Arrays.toString(test) + " to " + Arrays.toString(next(test))); } System.err.println("These can be next'd:"); for (int[] test : next) { System.err.println("\tNexted " + Arrays.toString(test) + " to " + Arrays.toString(next(test))); } } /** * Solves the 8-queens problem and outputs all solutions * @param partial The partial solution */ public static void solve(int[] partial) { if (reject(partial)) return; if (isFullSolution(partial)) System.out.println(Arrays.toString(partial)); int[] attempt = extend(partial); while (attempt != null) { solve(attempt); attempt = next(attempt); } } /** * Solves the 8-queens problem and returns one solution * @param partial The partial solution * @return A full, correct solution */ public static int[] solveOnce(int[] partial) { if (reject(partial)) return null; if (isFullSolution(partial)) return partial; int[] attempt = extend(partial); while (attempt != null) { int[] solution = solveOnce(attempt); if (solution != null) return solution; attempt = next(attempt); } return null; } public static void main(String[] args) { if (args.length >= 1 && args[0].equals("-t")) { testReject(); testIsFullSolution(); testExtend(); testNext(); } else if (args.length >= 1 && args[0].equals("-a")) { // Find all solutions starting from the empty solution solve(new int[] {0, 0, 0, 0, 0, 0, 0, 0}); } else { // Find one solution starting from the empty solution int[] solution = solveOnce(new int[] {0, 0, 0, 0, 0, 0, 0, 0}); System.out.println(Arrays.toString(solution)); } } } 

SemiMagic.java

package cs.a3; import java.util.Scanner; import java.io.File; import java.io.FileNotFoundException; public class SemiMagic { public static boolean isFullSolution(int[][] square) { // TODO: Complete this method return false; } public static boolean reject(int[][] square) { // TODO: Complete this method return false; } public static int[][] extend(int[][] square) { // TODO: Complete this method return null; } public static int[][] next(int[][] square) { // TODO: Complete this method return null; } static void testIsFullSolution() { // TODO: Complete this method } static void testReject() { // TODO: Complete this method } static void testExtend() { // TODO: Complete this method } static void testNext() { // TODO: Complete this method } /** * Returns a string representation of a number, padded with enough zeros to * align properly for the current size square. * @param num the number to pad * @param size the size of the square that we are padding to * @return the padded string of num */ static String pad(int num, int size) { // Determine the max value for a square of this size int max = size * size; // Determine the length of the max value int width = Integer.toString(max).length(); // Convert num to string String result = Integer.toString(num); // Pad string with 0s to the desired length while (result.length() < width) { result = " " + result; } return result; } /** * Prints a square * @param square the square to print */ public static void printSquare(int[][] square) { if (square == null) { System.out.println("Null (no solution)"); return; } int size = square.length; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { System.out.print(pad(square[i][j], size) + " "); } System.out.print(" "); } } /** * Reads a square of a specified size from a plaintext file * @param filename the name of the file to read from * @param size the size of the square in the file * @return the square * @throws FileNotFoundException if the named file is not found */ public static int[][] readSquare(String filename, int size) throws FileNotFoundException { Scanner scanner = new Scanner(new File(filename)); int[][] square = new int[size][size]; int val = 0; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { square[i][j] = scanner.nextInt(); } } return square; } /** * Solves the magic square * @param square the partial solution * @return the solution, or null if none */ public static int[][] solve(int[][] square) { if (reject(square)) return null; if (isFullSolution(square)) return square; int[][] attempt = extend(square); while (attempt != null) { int[][] solution; solution = solve(attempt); if (solution != null) return solution; attempt = next(attempt); } return null; } public static void main(String[] args) { if (args.length >= 1 && args[0].equals("-t")) { System.out.println("Running tests..."); testIsFullSolution(); testReject(); testExtend(); testNext(); } else if (args.length >= 1) { try { // First get the specified size int size = Integer.parseInt(args[0]); int[][] square; if (args.length >= 2) { // Read the square from the file square = readSquare(args[1], size); } else { // Initialize to a blank square square = new int[size][size]; } System.out.println("Initial square:"); printSquare(square); System.out.println(" Solution:"); int[][] result = solve(square); printSquare(result); } catch (NumberFormatException e) { // This happens if the first argument isn't an int System.err.println("First argument must be the size"); } catch (FileNotFoundException e) { // This happens if the second argument isn't an existing file System.err.println("File " + args[1] + " not found"); } } else { System.err.println("See usage in assignment description"); } } } 

Squares:

two.sq

1 0

0 0

three1.sq

2 7 6

0 0 0

0 0 0

three2.sq

2 0 0

0 7 0

0 0 6

five1.sq

11 0 7 0 0

4 0 0 0 0

0 0 0 21 0

10 0 0 0 0

0 0 19 0 0

five2.sq

11 0 5 0 0

4 0 0 2 0

0 3 0 21 0

0 0 0 0 12

6 1 19 0 0