Sudoku solve method

Question

I've a problem with my sudoku solving method. The program works like this; the board is empty when started, the users adds a couple of numbers to the board and then by hitting a Solve-button the program tries to solve it. Everything works fine besides if I put the same number in the same row. So if the user adds 1,1,0,0 ... 0. In the puzzle it can't solve it because its two 1's next to each other and will just go on forever trying to find a sulotion even though its an unsolvable puzzle. However if they were all 0's(empty) it would solve it right away, same as if Id put 1 and 2 in the top left corner. If I'd just put some random numbers in it will detect it as unsolvable (or will solve it if it's a valid puzzle)

I'm thinking around the lines of saying, when theNumber == (row, col) equals thenNumber == (row+1, col), it should return false because it's a duplicated number.

This is the code I tried to add in the solve method, obviously without success.

if ((puzzle.getNum(row, col) == a) == (puzzle.getNum(row + 1, col) == a)) {
   return false;
}

Help is greatly appreciated

Schlicher

Have you tried adding some sort of validation before attempting to "solve"? If you know right away the puzzle is unsolvable (two 1's in a row), then you don't want to infinite loop trying to solve. – Ceraceous

@Ceraceous Yes I tried doing some sort of validation method but I couldn't get it to work. This is my new attempt at "validating". And that's what I need help with. – Schlicher

changing variable names from a, i, j would make this much more readable. Or some comments would be greatly appreciated. I try to have meaningful variable names and it makes trouble-shooting much simpler. – Currier

@Currier Will go ahead and make a quick edit to my post. – Schlicher

Yeah, those variables should be changed – Stereotyped

I like java very much, but have some problems it is better to use others languages, for example, sudoku solver is a IA problem, and for it prolog is better then java, see this gist gist.github.com/ademar111190/3224223 can help you to see the sudoku problem with others eyes, remind, prolog can run inside java ;) – Inaccuracy

I'm sure he knows what the sovler is about. Just not how to actually write it. – Stereotyped

Answer 1

Validate the puzzle like this:

1. Create a boolean array of 9 elements.
2. Loop through every row, column and 9x9 box.
   • If you read a number, set the corresponding value in the array to true.
   • If it is already true throw an error (impossible puzzle).
   • After reading a row, column or 9x9 box reset the boolean array.
3. Then, if the validation succeeded call the solving method.

EDIT: Source code

public boolean checkPuzzle() {
    boolean[] nums = new boolean[9];
    for (int row = 0; row < panel.puzzleSize; row++) {
        for (int cell = 0; cell < panel.puzzleSize; cell++) {
            if (nums[puzzle[row][cell]]) return false;
            nums[puzzle[row][cell]] = true;
        }
        nums = new boolean[9];
    }
    for (int col = 0; col < panel.puzzleSize; col++) {
        for (int cell = 0; cell < panel.puzzleSize; cell++) {
            if (nums[puzzle[cell][col]]) return false;
            nums[puzzle[cell][col]] = true;
        }
        nums = new boolean[9];
    }
    for (int square = 0; square < panel.puzzleSize; square++) {
        int squareCol = panel.squareSize * (square % panel.squareSize);
        int squareRow = panel.squareSize * Math.floor(square / panel.squareSize);
        for (int cell = 0; cell < panel.puzzleSize; cell++) {
            int col = cell % panel.squareSize;
            int row = Math.floor(cell / panel.squareSize);
            if (nums[puzzle[squareCol + col][squareRow + row]]) return false;
            nums[puzzle[squareCol + col][squareRow + row]] = true;
        }
        nums = new boolean[9];
    }
    return true;
}

Didn't have too much time to test out, but it might work (?). The row/col variable namings might be incorrect, because I didn't have time to find that in your code, but it shouldn't matter for it to work or not.

Linsang

How would that code look like in my method? Since I'm having a hard time actually implementing some sort of validation method. I understand that I need to loop through my rows, columns but I'm not really sure how to do step number 2. – Schlicher

You must do it before calling the solving method (the one that repeatedly calls check(). I suggest that you use three loops to loop through rows, cols and 9x9 blocks. Then inside them implement code that updates the boolean array and checks for same numbers. I can't provide code because I don't know how your solving code looks except for the check() method. You should do it like if (boolean_array[found_number]) { /* fail */ } boolean_array[found_number] = true;. – Linsang

I will go ahead and try your suggestion, in the meanwhile I edited my main post and added my source. – Schlicher

i will take a look at the sources and try writing some code but don't expect wonders as im quite new to java – Stereotyped

@Pietu1998 Damn, I cant seem to get it working. How's it going on your end, did you check out the source code? – Schlicher

OK. So before you call solve(0, 0) you should do the validation thing. Also re-solving it to check if it was solved might not be the best way; I'm not sure if it is necessary. Try removing the first solve(0, 0) call. – Linsang

@Schlicher Yes. I'll have to go, tell in the comments/accept if correct, I will get back to you tomorrow (~20hours because of school). – Linsang