Sudoku Brute Force Algorithm

Question

I have to program a Brute Force Algorithm to solve a Sudoku with predetermined methods. I am kind of on a mental block as for the solve method. The assignment says we have to use at least the given methods, which are isPermutation, isPermutationRow, isPermutationCol, isPermutationBlock, isPermutationMatrix, isValid and solve.

I don't really have an idea on when to return values within the solve method, given that it has to be recursive.

I would be really thankful for any help :)

package gdp.aufgabe22;

public class Sudoku {

public static void main(String[] args) {
    int[][] d = { {0,0,3,0,2,0,6,0,0},
                  {9,0,0,3,0,5,0,0,1},
                  {0,0,1,8,0,6,4,0,0},
                  {0,0,8,1,0,2,9,0,0},
                  {7,0,0,0,0,0,0,0,8},
                  {0,0,6,7,0,8,2,0,0},
                  {0,0,2,6,0,9,5,0,0},
                  {8,0,0,2,0,3,0,0,9},
                  {0,0,5,0,1,0,3,0,0}
    };
    int[][] s = solve(d);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            System.out.print(s[i][j] + " ");
        }
        System.out.print("\n");
    }
    System.out.println();
}

public static boolean isPermutation(int[] a) {
    int[][] key = new int[2][a.length];
    key[0] = a;
    for (int i = 0; i < key.length; i++) {
        key[1][i] = 0;
    }
    for (int i = 0; i < key.length; i++) {
        if (a[i]>0) {
            key[1][a[i]-1]++;
        }
    }
    boolean keycheck = false;
    for (int i = 0; i < a.length; i++) {
        if(key[1][i]>1) {
            keycheck = true;
        }
    }
    if (keycheck == true) {
        return false;
    }
    else {
        return true;
    }
}

public static boolean isPermutationRow(int[][] a, int row) {
        int[] key = new int[a[row].length];
        key = a[row];
        return isPermutation(key);
}

public static boolean isPermutationCol(int[][] a, int col) {
    int[] key = new int[a.length];
    for (int i = 0; i < key.length; i++) {
        key[i] = a[i][col];
    }
    return isPermutation(key);
}

public static boolean isPermutationMatrix(int[][] a) {
    for (int i = 0; i < a.length; i++) {
        if (!isPermutationRow(a, i)) {
            return false;
        }
    }
    for (int i = 0; i < a.length; i++) {
        if (!isPermutationCol(a, i)) {
            return false;
        }
    }
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            switch (i) {
            case 0: switch(j) {
                case 0: if(!isPermutationBlock(a,0,2,0,2)) {
                    return false;
                }
                case 3: if(!isPermutationBlock(a,0,2,3,5)) {
                    return false;
                }
                case 6: if(!isPermutationBlock(a,0,2,6,8)) {
                    return false;
                }
                default: break;
            }
            case 3: switch(j) {
                case 0: if(!isPermutationBlock(a,3,5,0,2)) {
                    return false;
                }   
                case 3: if(!isPermutationBlock(a,3,5,3,5)) {
                    return false;
                }
                case 6: if(!isPermutationBlock(a,3,5,6,8)) {
                    return false;
                }
                default: break;
            }   
            case 6: switch(j) {
                case 0: if(!isPermutationBlock(a,6,8,0,2)) {
                    return false;
                }   
                case 3: if(!isPermutationBlock(a,6,8,3,5)) {
                    return false;
                }
                case 6: if(!isPermutationBlock(a,6,8,6,8)) {
                    return false;
                }
                default: break;
            }   
            default: break;
        }
        }
    }
    return true;
}

public static boolean isPermutationBlock(int[][] a, int minRow, int maxRow, int minCol, int maxCol) {
    int[][] key = new int[2][(maxRow-minRow+1)+(maxCol-minCol+1)];
    int[][] countfeld = new int[2][9];
    for (int i = 0; i < 9; i++) {
        countfeld[0][i] = i+1;
    }
    int keycount = 0;
    for (int i = minRow; i<maxRow; i++) {
        for (int j = minCol; j<maxCol; j++) {
            key[0][keycount] = a[i][j];
            keycount++;
        }
    }
    for (int i = 0; i < countfeld[0].length; i++) {
        countfeld[1][i] = 0;
    }
    for (int i = 0; i < key[0].length; i++) {
        if (key[0][i]>0) {
            countfeld[1][key[0][i]-1]++;
        }
    }
    boolean keycheck = false;
    for (int i = 0; i < key[0].length; i++) {
        if(countfeld[1][i]>1) {
            keycheck = true;
        }
    }
    if (keycheck == true) {
        return false;
    }
    else {
        return true;
    }
}

public static boolean isValid(int[][] a) {
    if (a.length != 9 || a[0].length != 9) {
        return false;
    }
    return (isPermutationMatrix(a));
}

public static int[][] solve(int[][] a) {
    int[] freeslot = findfreeslot(a);
    int f1 = freeslot[0];
    int f2 = freeslot[1];
    if (f1 == -1) {
        return a;
    }
    teilsolve(f1, f2, a);
    return a;
}

public static void teilsolve(int f1, int f2, int[][] a) {
    int[][] temp = new int[a.length][a[0].length];
    for (int y = 0; y < a.length; y++) {
        for (int z = 0; z < a[0].length; z++) {
            temp[y][z] = a[y][z];
        }
    }
    for (int i = 1; i < 10; i++) {
        a[f1][f2] = i;
        boolean valide = isValid(a);
        if (valide) {
            a = solve(a);
            break;
        }
    }
}

public static int[] findfreeslot(int[][]a) {
    int[] key = {-1,-1};
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (a[i][j] == 0) {
                key[0] = i;
                key[1] = j;
                return key;
            }
        }
    }
    return key;
}
}

Answer 1

You have a number of problems in your code.

First, the method isPermutation is wrong : you loop until key.length which is 2 when you should loop up to 9 a.length ! The method should be :

public static boolean isPermutation(int[] a) {
    int[][] key = new int[2][a.length];
    key[0] = a;
    for (int i = 0; i < a.length; i++) {
        key[1][i] = 0;
    }
    for (int i = 0; i < a.length; i++) {
        if (a[i] > 0) {
            key[1][a[i] - 1]++;
        }
    }
    boolean keycheck = false;
    for (int i = 0; i < a.length; i++) {
        if (key[1][i] > 1) {
            keycheck = true;
            break;
        }
    }
    if (keycheck == true) {
        return false;
    } else {
        return true;
    }
}

As noted by Patrick J Abare II, the end should really be return ! keycheck;

Next you try to use brute force, but never backtrack. The pair of methods solve, teilsolve should deal with unacceptable values at any level and should be :

public static int[][] solve(int[][] a) {
    int[] freeslot = findfreeslot(a);
    int f1 = freeslot[0];
    int f2 = freeslot[1];
    if (f1 == -1) {
        return a;
    }
    a = teilsolve(f1, f2, a);
    return a;
}

public static int [][] teilsolve(int f1, int f2, int[][] a) {
    int [][] temp2;
    int[][] temp = new int[a.length][a[0].length];
    for (int y = 0; y < a.length; y++) {
        for (int z = 0; z < a[0].length; z++) {
            temp[y][z] = a[y][z];
        }
    }
    for (int i = 1; i < 10; i++) {
        temp[f1][f2] = i;
        boolean valide = isValid(temp);
        if (valide) {
            temp2 = solve(temp);
            if (temp2 != null) {return temp2;}
        }
    }
    return null;
}

That way, the program returns :

4 5 3 9 2 1 6 8 7 
9 2 7 3 6 5 8 4 1 
2 3 1 8 9 6 4 7 5 
5 4 8 1 7 2 9 3 6 
7 6 9 5 3 4 1 2 8 
1 9 6 7 4 8 2 5 3 
3 7 2 6 8 9 5 1 4 
8 1 4 2 5 3 7 6 9 
6 8 5 4 1 7 3 9 2 

Answer 2

Just some general advice:

I think you got lost because honestly, that code is a mess.

So, first advice: Clean up that code. Just compare your isPermutation(int[]) method with the following - which one is easier to read? You can't really figure out why your code doesn't work if you cannot even read, let alone comprehend, it. Mind you, the inline comments are pretty verbose, but just using meaningful names for your variables helps a LOT.

/**
 * Checks whether the array is a valid permutation of all natural numbers within its length.
 * 
 * @param lineToCheck
 *            a line in sudoku, regardless of direction
 * @return whether the line is valid
 */
public static boolean isPermutation(int[] lineToCheck) {
    // numbersPerLine - will usually be nine, could be anything
    int numbersPerLine = lineToCheck.length;

    // for every number that should exist in the line...
    for (int currentExpectedNumber = 1; currentExpectedNumber <= numbersPerLine; currentExpectedNumber++) {
        boolean foundCurrentNumber = false;

        // ...check whether it is anywhere in the line.
        for (int numberInLine : lineToCheck) {
            if (currentExpectedNumber == numberInLine) {
                // great, we found the number, so check the next one
                foundCurrentNumber = true;
                break;
            }
        }
        if (!foundCurrentNumber) {
            /*
             * if we got here, the expected number could not be found anywhere in the line, so the line is NOT a valid permutation
             */
            return false;
        }
    }
    // all numbers were found, so we do in fact have a valid permutation
    return true;
}

Next advice: Figure out what exactly it is you are trying to do. You are probably aware there are several Sudoku solving algorithms. Line up the steps of the algorithm you are trying to implement with the steps your code takes. You should be able to walk through the whole thing and spot the differences. Work on those.