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. 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.

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. Below is the provided code:

Please fill in the to do portions (must use backtracking) in java

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"); } } }