rendered paste bodypublic class TKsolver { /** * @param args */ public static void main(String[] args) { TKsolver tk = new TKsolver(4); int[] start = new int[16]; int[] valid = new int[] { 1, 15, 14, 4, 12, 6, 7, 9, 8, 10, 11, 5, 13, 3, 2, 16 }; for (int j = 0; j < 16; j++) { valid[j] = 0; } int[] solution = null; long startTime = System.currentTimeMillis(); solution = tk.solveBoard2(new int[tk.orderSQ]); long stopTime = System.currentTimeMillis(); System.out.println("Time to solve is " + (stopTime - startTime) + "ms"); tk.showBoard(solution); // tk.showList(tk.validate(valid)); } int magicNumber; int order; private int orderSQ; public TKsolver(int order) { magicNumber = (order * order * order + order) / 2; this.order = order; this.orderSQ = order * order; System.out.println("ready to solve a magicsquare with order " + order + "\nThe magicnumber vill be " + magicNumber + " and there are " + orderSQ + " squares"); } public int[] solveBoard(int[] board) { int firstFree = -1; int idx = 0; int[] missing = new int[orderSQ]; for (int i = 0; i < orderSQ; i++) { if (!contains(board, i + 1)) missing[idx++] = i + 1; if (firstFree < 0 && board[i] == 0) firstFree = i; } if (firstFree < 0) return validate(board); int[] solution = null; for (int i : missing) { if (i != 0) { int[] nb = board.clone(); nb[firstFree] = i; if (!validSoFar(nb)) continue; solution = solveBoard(nb); if (solution != null) break; } } return solution; } public int[] solveBoard2(int[] board) { int firstFree = -1; boolean[] used = new boolean[orderSQ]; for (int i = 0; i < board.length; i++) { int x = board[i]; if (x == 0) { used[x] = true; if (firstFree < 0) firstFree = i; } } if (firstFree < 0) return validate(board); int[] solution = null; for (int i = 0; i < used.length; i++) { if (!used[i]) { int[] nb = board.clone(); nb[firstFree] = i + 1; if (!rowValidSoFar(nb)) continue; solution = solveBoard(nb); if (solution != null) break; } } return solution; } private boolean rowValidSoFar(int[] nb) { int rowSum = 0; for (int i = 0; i < order; i++) { rowSum = 0; for (int j = 0; j < order; j++) { int y = nb[i * order + j]; if (y != 0) rowSum += y; else return true; } if (rowSum!=magicNumber) return false; } return true; } private boolean validSoFar(int[] nb) { int rowSum = 0; boolean moreRows = true; int[] colCumulative = new int[order]; boolean[] colExhausted = new boolean[order]; for (int i = 0; i < order; i++) { rowSum = 0; for (int j = 0; j < order; j++) { int y = nb[i * order + j]; if (y != 0) { if (!colExhausted[j]) colCumulative[j] += y; if (moreRows) rowSum += y; } else { moreRows = false; colExhausted[j] = true; } } if (moreRows) { if (rowSum != magicNumber) return false; } else { boolean allExhausted = true; for (int j = 0; j < colExhausted.length; j++) { allExhausted &= colExhausted[j]; } if (allExhausted) return true; } } for (int i = 0; i < colCumulative.length; i++) { if (!colExhausted[i] && colCumulative[i] != magicNumber) { return false; } } return true; } private boolean contains(int[] a, int x) { boolean found = false; for (int i : a) { if (i == x) { found = true; break; } } return found; } private int[] validate(int[] board) { int colSum = 0; int rowSum = 0; for (int i = 0; i < order; i++) { colSum = rowSum = 0; for (int j = 0; j < order; j++) { colSum += board[i * order + j]; rowSum += board[i + j * order]; } if (colSum != rowSum) return null; } int diag = 0; for (int i = 0; i < order; i++) { diag += (board[i * order + i] - board[i * order + (order - i) - 1]); } if (diag != 0) return null; return board; } private void showBoard(int[] board) { int idx = 0; for (int i : board) { System.out.print(i + ((++idx % order == 0) ? "\n" : "\t")); } }}