3

The 3x3 magic square I'm working with is filled with numbers 1-9. The values in each row, column, and diagonal must add to 15. I must follow this pseudocode:

recursive_funtion(position) {  
    for number from 1 to 9, not used elsewhere already {  
        put this number on this position, make it unavailable  
        if solution valid {  
            if solution complete {  
                done, show solution  
            }else{  
                recursive_function(next_position)  
            }  
        }  
        (make this space blank again, and the number available)  
    }  
}

I have it working until it goes through the first row and realizes that after adding a 1 in the top left spot and and 2 in the top middle spot, there is no way to make 15 in that row. Is anyone able to see where I'm making a mistake or fill in any logic that I'm missing? Thanks.

public class MagicSquare {

    private int[][] magicSquare;
    private boolean[] available;

    public MagicSquare() {
        magicSquare = new int[3][3];
        available = new boolean[9];
        for (int i = 0; i < available.length; i++) {
            available[i] = true;
        }
    }

    public void run() {
        System.out.println("Magic Square Puzzle");
        solve(0, 0);
    }

    public boolean solve(int row, int col) {
    for (int i = 1; i <= 9; i++) {
        if (isAvailable(i)) {
            System.out.println("placing " + i + " at (" + row + ", " + col + ")");
            magicSquare[row][col] = i;
            available[i - 1] = false;
            //solution is valid so far
            if (isFilledRow(row)) {
                if (isValidRow(row) && isValidCol(col)) {
                    if (solve(row, col)) {
                        return true;
                    } else {
                        magicSquare[row][col] = 0;
                        magicSquare[row][col - 1] = 0;
                        col = col - 1;
                        available[magicSquare[row][col] - 1] = false;
                        solve(row, col);
                    }
                }
            }
            if (!isFilledRow(row)) { //check logic here!
                if (isValidSolution()) {
                    System.out.println("You found a correct solution!");
                    printSolution();
                } else {
                    //new row
                    if (col == 2 && row != 2) {
                        row = row + 1;
                        System.out.println("new row and solve(" + row + ", " + col + ")");
                        solve(row, 0);
                        //new col    
                    } else if (col != 2) {
                        col = col + 1;
                        System.out.println("new col and solve(" + row + ", " + col + ")");
                        solve(row, col);
                    } else if (row == 2 && col == 2) {
                        //check logic here!

                    }
                }
            } 
            magicSquare[row][col] = 0;
            available[i - 1] = true;
        }
    }
    return false;
}

    public boolean isAvailable(int value) {
        if (available[value - 1] == true) {
            System.out.println(value + " is available to be placed");
            return true;
        } else {
            System.out.println(value + " is not available to be placed");
            return false;
        }
    }

    public boolean isFilledRow(int row) {
        if (magicSquare[row][0] != 0 && magicSquare[row][1] != 0 && magicSquare[row][2] != 0) {
            System.out.println("row " + row + " is filled");
            return true;
        } else {
            //System.out.println("row " + row + " is not filled");
            return false;
        }

    }

    public boolean isValidRow(int row) {
        if (magicSquare[row][0] + magicSquare[row][1] + magicSquare[row][2] == 15) {
            System.out.println("row " + row + " adds to 15");
            return true;
        } else {
            System.out.println("row " + row + " does not add to 15");
            return false;
        }
    }

    public boolean isValidCol(int col) {
        if (magicSquare[0][col] + magicSquare[1][col] + magicSquare[2][col] == 15) {
            System.out.println("col " + col + " adds to 15");
            return true;
        } else {
            //System.out.println("col " + col + " does not add to 15");
            return false;
        }
    }

    public boolean isValidOnDiagonals() {
        if ((magicSquare[0][0] + magicSquare[1][1] + magicSquare[2][2] == 15) && (magicSquare[2][0] + magicSquare[1][1] + magicSquare[0][2] == 15)) {
            System.out.println("diagonals add to 15");
            return true;
        } else {
            //System.out.println("diagonals don't add to 15");
            return false;
        }
    }

    public boolean isValidSolution() {
        for (int i = 0; i < magicSquare.length; i++) {
            if (isValidRow(i) && isValidCol(i) && isValidOnDiagonals()) {
                System.out.println("solution is valid");
                return true;
            }
        }
        //System.out.println("solution is not valid");
        return false;
    }

    public void printSolution() {
        for (int i = 0; i < magicSquare.length; i++) {
            for (int j = 0; j < magicSquare[i].length; j++) {
                System.out.print(magicSquare[i][j] + " ");
            }
            System.out.println();
        }
    }
}
CS student
  • 305
  • 1
  • 3
  • 13
  • For a given filled square, you must test if a/ it fills any row/column, and if so if it conforms to the constraints and b/ if by using that value you are able to complete the problem, i.e. if your recursion results in a valid solution. If not, you need to blank your square and try the next value. If you have tried all values, return false. – njzk2 Jul 30 '15 at 02:54
  • basically you need to be able to backtrack your steps until you solve the problem. For example, one of the point where you may end is `[[1, 5, 9], [4, 8, 3], [0, 0, 0]]`. At this point, you need to backtrack 3 steps to be able to get to `[[1, 5, 9], [6, 0, 0], [0, 0, 0]]` which will give you the solution – njzk2 Jul 30 '15 at 03:33
  • @njzk2 I edited my solve method, attempting to follow step a from above. Where do I implement backtracking? Could you give me an example of what backtracking might look like? – CS student Jul 30 '15 at 03:36
  • Usually it involves making your `solve` method return a boolean, false as soon as you reach a dead end (when you have tried all available values for a cell), or true when the problem is solved. What you have to do to use it is, when you have a value that is not a contradiction (invalid filled row or col) nor a solution, test the result of calling the recursive function. If true, return true, if false, try with another value. In your first example, once you have `[1,2,9]`, you return false because you have tested `[3,4,5,6,7,8,9]`, which means for the calling method that 2 is invalid, try 3. – njzk2 Jul 30 '15 at 03:42

1 Answers1

1

A few issues:

  • isValidSolution() can return true even if the square is not valid.
  • Your solve() method's logic got a bit too complicated. I tried simplifying it.
  • Having so many System.out.println statements actually has a massive impact on execution time of your algorithm. So I commented out most of them.

I'm sure you can keep improving this, and at the moment, it doesn't stop after finding the first solution. It actually prints out all solutions.

Hopefully you can use this to get you closer to your final/polished algorithm:

public class MagicSquare {

    private int[][] magicSquare;
    private boolean[] available;

    public MagicSquare() {
        magicSquare = new int[3][3];
        available = new boolean[9];
        for (int i = 0; i < available.length; i++) {
            available[i] = true;
        }
    }

    public void run() {
        System.out.println("Magic Square Puzzle");
        solve(0, 0);
    }

    public void solve(int row, int col) {
    for (int i = 1; i <= 9; i++) {
        if (isAvailable(i)) {
            //System.out.println("placing " + i + " at (" + row + ", " + col + ")");
            magicSquare[row][col] = i;
            available[i - 1] = false;
            //solution is valid so far
            if (isFilled()) {
                if (isValidSolution()) {
                    System.out.println("You found a correct solution!");
                    printSolution();
                }
            } else {
                if (col != 2) {
                    //System.out.println("new col and solve(" + row + ", " + col + ")");
                    solve(row, col + 1);
                } else if (row != 2) {
                    //System.out.println("new row and solve(" + row + ", " + col + ")");
                    solve(row + 1, 0);
                    //new col    
                }
            }
            magicSquare[row][col] = 0;
            available[i - 1] = true;
        }
    }
}

    public boolean isAvailable(int value) {
        if (available[value - 1] == true) {
            //System.out.println(value + " is available to be placed");
            return true;
        } else {
            //System.out.println(value + " is not available to be placed");
            return false;
        }
    }

    public boolean isValidRow(int row) {
        if (magicSquare[row][0] + magicSquare[row][1] + magicSquare[row][2] == 15) {
            //System.out.println("row " + row + " adds to 15");
            return true;
        } else {
            //System.out.println("row " + row + " does not add to 15");
            return false;
        }
    }

    public boolean isValidCol(int col) {
        if (magicSquare[0][col] + magicSquare[1][col] + magicSquare[2][col] == 15) {
            //System.out.println("col " + col + " adds to 15");
            return true;
        } else {
            //System.out.println("col " + col + " does not add to 15");
            return false;
        }
    }

    public boolean isValidOnDiagonals() {
        if ((magicSquare[0][0] + magicSquare[1][1] + magicSquare[2][2] == 15) && (magicSquare[2][0] + magicSquare[1][1] + magicSquare[0][2] == 15)) {
            //System.out.println("diagonals add to 15");
            return true;
        } else {
            //System.out.println("diagonals don't add to 15");
            return false;
        }
    }

    public boolean isValidSolution() {
        for (int i = 0; i < magicSquare.length; i++) {
            if (!isValidRow(i) || !isValidCol(i)) {
                //System.out.println("solution is valid");
                return false;
            }
        }
        //System.out.println("solution is not valid");
        return isValidOnDiagonals();
    }

    public boolean isFilled() {
        for (int i = 0; i < available.length; i++) {
            if (available[i]) {
                return false;
            }
        }
        return true;
    }

    public void printSolution() {
        for (int i = 0; i < magicSquare.length; i++) {
            for (int j = 0; j < magicSquare[i].length; j++) {
                System.out.print(magicSquare[i][j] + " ");
            }
            System.out.println();
        }
    }
}
sstan
  • 35,425
  • 6
  • 48
  • 66