5 Replies - 1212 Views - Last Post: 27 July 2012 - 05:37 AM Rate Topic: -----

#1 mciomes  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 22
  • Joined: 18-July 12

Magic Squares problem using recursion won't check validity of row

Posted 26 July 2012 - 01:43 PM

Hello hello,

I'm working on a program that asks the user for an integer that will be used as the order for a Magic Square. I've set up the constructor, the addVal, the removeVal, and the Solve, methods. I think the problem is now somewhere in my isValid method. When I run the program it returns a not so magic square with the integers appearing in the square 1 through N*N. I'm completely at a loss at this point on what the problem is. I'm almost certain it's the isValid method, but I don't see what's causing the problem when it tries to add up the values. Any help would be appreciated, here's what I have so far:


import java.util.*;

public class MagicSquare {
    // the current contents of the cells of the puzzle values[r][c]
    // gives the value in the cell at row r, column c
    private int[][] values;
    private int order; // the order (i.e., the dimension) of the puzzle
    private boolean [] available;  // numbers still available to be added to the magic square
    private int totalSquares; // total number of squares on the board
    private int sum;  // sum that the rows and columns must add up to

 
    public MagicSquare(int order)
         {
                values = new int[order][order];
                this.order = order;
                totalSquares = order * order;
                sum = (order * order * order + order)/2;
                for (int i = 0; i < order; i++)
                {
                        for (int j = 0; j < order; j++)
                        {
                                values[i][j] = 0;
                        }
                }
                available = new boolean[totalSquares];
                for (int i = 0; i < totalSquares; i++)
                {
                        available[i] = true;
                }

        }


  public void removeVal(int i, int row, int col)
        {
                values[row][col] = 0;
                available[i] = true;
        }

  public boolean addVal(int row, int col)
        {
                System.out.println(row + "" + col);
                if (row == order - 1 && col == order)
                {
                         display();
                        return true;
                }
                for(int i = 1; i <= totalSquares; i++)
                {
                        if(isValid(i, row, col))
                        {
                                values[row][col] = i;
                                available[i] = false;
                                int newCol, newRow;
                                if (col == order - 1)
                                        newCol = 0;
                                else
                                        newCol = col + 1;

                                if (newCol == 0) newRow = row+1;
                                else
                                        newRow = row;
                                if (addVal(newRow, newCol)) return true;
                                else removeVal(i, row, col);
                        }
                }
                return false;
        }


   public boolean isValid(int i, int row, int col)
        {
                if (available[i] == false) return false;
                int colCount = 0;
                int rowCount = 0;
                int colSum = 0;
                int rowSum = 0;
                for( int j = 0; j < order; j ++)
                {
                        System.out.println("col is " + col);
                        System.out.println("j is " + j);
                        System.out.println("row is " + row);
                        if (values[j][col] == 0) colCount ++;
                        if (values[row][j] == 0) rowCount ++;
                        rowSum += values[row][j];
                        colSum += values[j][col];
                        display();
                }
                System.out.println("colSum is " + colSum);
                System.out.println("rowSum is " + rowSum);
                if (colCount == 1)
                {
                        if (i + colSum == sum && i + rowSum == sum) return true;
                }
                if (rowCount == 1)
                {
                        if (i + colSum == sum && i + rowSum == sum) return true;
                }
                else if (i + colSum > sum || i + rowSum > sum) return false;
                return true;
        }


   public boolean solve()
         {
                if (addVal(0,0)) return true;
                else return false;
         }

    public void display() {
        for (int r = 0; r < order; r++) {
            printRowSeparator();
            for (int c = 0; c < order; c++) {
                System.out.print("|");
                if (values[r][c] == 0)
                    System.out.print("   ");
                else {
                    if (values[r][c] < 10) {
                        System.out.print(" ");
                    }
                    System.out.print(" " + values[r][c] + " ");
                }
            }
            System.out.println("|");
        }
        printRowSeparator();
    }


    private void printRowSeparator() {
        for (int i = 0; i < order; i++)
            System.out.print("-----");
        System.out.println("-");
    }


 public static void main(String[] args) {

        Scanner console = new Scanner(System.in);
        System.out.print("What order Magic Square would you like to solve? ");
        int order = console.nextInt();

        MagicSquare puzzle = new MagicSquare(order);
        if (puzzle.solve()) {
            System.out.println("Here's the solution:");
            puzzle.display();
        } else {
            System.out.println("No solution found.");
        }
    }
}




As I said, I think the problem is with my isValid method, but I'm not positive. I'm afraid to change anything else right now because as far as I can tell the other methods are ok. Thanks for any help!

Is This A Good Question/Topic? 0
  • +

Replies To: Magic Squares problem using recursion won't check validity of row

#2 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2198
  • View blog
  • Posts: 5,226
  • Joined: 10-September 10

Re: Magic Squares problem using recursion won't check validity of row

Posted 26 July 2012 - 03:00 PM

Can you describe how your algorithm is supposed to work? More comments in your code would be helpful.
Was This Post Helpful? 0
  • +
  • -

#3 mciomes  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 22
  • Joined: 18-July 12

Re: Magic Squares problem using recursion won't check validity of row

Posted 26 July 2012 - 03:24 PM



import java.util.*;

public class MagicSquare {
    // the current contents of the cells of the puzzle values[r][c]
    // gives the value in the cell at row r, column c
    private int[][] values;

    // the order (i.e., the dimension) of the puzzle
    private int order;

    private boolean [] available;  // numbers still available to be added to the magic square
    private int totalSquares; // total number of squares on the board
    private int sum;  // sum that the rows and columns must add up to

    /**
     * Creates a MagicSquare object for a puzzle with the specified
     * dimension/order.
     */
    public MagicSquare(int order)  // this initializes all the values to 0 on the board, and initializes all numbers as available
         {
                values = new int[order][order];
                this.order = order;
                totalSquares = order * order;
                sum = (order * order * order + order)/2;
                for (int i = 0; i < order; i++)
                {
                        for (int j = 0; j < order; j++)
                        {
                                values[i][j] = 0;
                        }
                }
                available = new boolean[totalSquares];
                for (int i = 0; i < totalSquares; i++)
                {
                        available[i] = true;
                }

        }


public void removeVal(int i, int row, int col)  // removes a value if it is found to be incorrect on the board
        {
                values[row][col] = 0;
                available[i] = true;
        }

        public boolean addVal(int row, int col)  // adds values recursively, checking to make sure they fit on the board
        {
                System.out.println(row + "" + col);
                if (row == order - 1 && col == order)
                {
                         display();
                        return true;
                }
                for(int i = 1; i <= totalSquares; i++)
                {
                        if(isValid(i, row, col))
                        {       
                                values[row][col] = i;                                                                                        
                                available[i] = false;
                                int newCol, newRow;
                                if (col == order - 1)
                                        newCol = 0;
                                else
                                        newCol = col + 1;

                                if (newCol == 0) newRow = row+1;
                                else
                                        newRow = row;
                                if (addVal(newRow, newCol)) return true;
                                else removeVal(i, row, col);
                        }
                }
                return false;
        }

        public boolean isValid(int i, int row, int col)  //checks to make sure the value given fits as it is placed on the board, and to make sure that the sum of the rows / columns is //correct
        {
                if (available[i] == false) return false;
                int colCount = 0;
                int rowCount = 0;
                int colSum = 0;
                int rowSum = 0;
                for( int j = 0; j < order; j ++)
                {
                        System.out.println("col is " + col);
                        System.out.println("j is " + j);
                        System.out.println("row is " + row);
                        if (values[j][col] == 0) colCount ++;
                        if (values[row][j] == 0) rowCount ++;
                        rowSum += values[row][j];
                        colSum += values[j][col];
                        display();
                }
                System.out.println("colSum is " + colSum);
                System.out.println("rowSum is " + rowSum);
                if (colCount == 1)
                {
                        if (i + colSum == sum && i + rowSum == sum) return true;
                }
                if (rowCount == 1)
                {
                        if (i + colSum == sum && i + rowSum == sum) return true;
                }
                else if (i + colSum > sum || i + rowSum > sum) return false;
                return true;
        }


         public boolean solve() // returns true to allow the board to print in main
         {
                if (addVal(0,0)) return true;
                else return false;
         }

// displays the current state of the puzzle 

  public void display() {
        for (int r = 0; r < order; r++) {
            printRowSeparator();
            for (int c = 0; c < order; c++) {
                System.out.print("|");
                if (values[r][c] == 0)
                    System.out.print("   ");
                else {
                    if (values[r][c] < 10) {
                        System.out.print(" ");
                    }
                    System.out.print(" " + values[r][c] + " ");
                }
            }
            System.out.println("|");
        }
        printRowSeparator();
    }

    // A private helper method used by display()
    // to print a line separating two rows of the puzzle.
    private void printRowSeparator() {
        for (int i = 0; i < order; i++)
            System.out.print("-----");
        System.out.println("-");
    }

    public static void main(String[] args) {

        Scanner console = new Scanner(System.in);
        System.out.print("What order Magic Square would you like to solve? ");
        int order = console.nextInt();

        MagicSquare puzzle = new MagicSquare(order);
        if (puzzle.solve()) {
            System.out.println("Here's the solution:");
            puzzle.display();
        } else {
            System.out.println("No solution found.");
        }
    }
}




I've added comments on what the methods are supposed to do. The magic square should be such that an n x n square will have values in each row and column such that every row and every column adds up to (n^3 + n )/2.
Was This Post Helpful? 0
  • +
  • -

#4 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2198
  • View blog
  • Posts: 5,226
  • Joined: 10-September 10

Re: Magic Squares problem using recursion won't check validity of row

Posted 26 July 2012 - 04:01 PM

I was hoping for a description of your algorithm something like:

If the user inputs a 3, my program tries all possible 3x3 solutions using the numbers 1 - 9, checking that the sum of each row, column, and diagonal is the magic number until a solution is found. If all possible combinations are attempted and a solution is not found, the algorithm reports that there is no solution. (A typical Brute Force algorithm.)

If you were to describe your algorithm as I have above, I would ask why your solution prints partial results rather than all possible 3x3 possible solutions.

I would also ask if you're getting any errors, because when I run your program I'm getting:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 9

because line 55 should be:

for(int i = 1; i < totalSquares; i++)

and I would wonder why you're not seeing and reporting the error.
Was This Post Helpful? 0
  • +
  • -

#5 mciomes  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 22
  • Joined: 18-July 12

Re: Magic Squares problem using recursion won't check validity of row

Posted 26 July 2012 - 04:16 PM

That's strange, I must've missed that before because when I was running it earlier the problem wasn't an OutofBounds exception. I changed line 55 and ran it, now its giving me a solution not found, so I think that means the problem is definitely in my isValid method. It looks like the sums aren't adding up properly. I'm looking at lines 97 to 106, because I think that's where the problem should be, but I don't see anything wrong with it. colSum and rowSum should add up to the values of the given row or column, and if there is one 0 value left then that should mean it's on the last run through for the given row or column. Am I missing something?
Was This Post Helpful? 0
  • +
  • -

#6 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2198
  • View blog
  • Posts: 5,226
  • Joined: 10-September 10

Re: Magic Squares problem using recursion won't check validity of row

Posted 27 July 2012 - 05:37 AM

Again, it's hard to help you fix the solution algorithm without understanding how it's supposed to work.

I've studied it some, and it seems to me that the recursive addVal() method and the isValid() method have to work together, and I'm not sure they are. addVal() starts at value i = 1, row = 0, col = 0 and passes those to isValid() for a check.

According to your comment, isValid() then ensures the value (i = 1) fits on the board. isValid() then checks the row and column sums for correctness.

What's to check with one value in the board? All column, row, and diagonal (do you check those?) sums can't possibly be correct with less than order * order values on the board . As best I can tell, your algorithm never gets to 9 values on the board for an order 3 square.

It seems to me that the solver would start with the board full of possible values and the solution algorithm would then vary the position of the values until a solution was found or all possible solutions were considered, and it was determined that a solution didn't exist.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1