Anonymous

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

}