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();
}
}
}
A few issues:
isValidSolution() can return true even if the square is not valid.solve() method's logic got a bit too complicated. I tried simplifying it.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();
}
}
}