Problem 96 - Java

So, Problem 96 involves solving Sudoku puzzles. I honestly had a lot more difficulty with this problem than I needed to. Among my issues were trying to be fancier than necessary. Only doing the "first step" of logical deduction is entirely sufficient before going into guess and check, and my attempts at implementing the guess and check were truly ugly prior to coming across the somewhat nice/clean recursion that I ended up with. I think a lot of my issue with this problem is just that I moved from trying to do this in Pike, where I had crazy ideas that were limited by the language's data structures, so then I tried to use those same structures in Java because, why not, Java is object oriented, while in the end simplicity won. (Basically for a long time I had a stack of boards that was hard to manage, rather than just having stack-like stuff done through recursion).

My final issue with this problem was a very stupid one. I kept trying to debug errors because my output was clearly wrong, far less than what the correct answer would have to look like. Turns out adding three digits together is very different from concatenating them together. And now that this rather frustrating problem is done, hopefully the next 3 to get to 100 won't be too bad.

Solution runs in about .5s on my machine.

import java.util.*;

//Because you can't have arrays of Generics
//Because Java is silly
class HashSetInteger extends HashSet<Integer> { }

public class e96 {

public static int[][] copyArray(int[][] arr) {
    int ret[][] = new int[arr.length][arr[0].length];
    for (int i = 0; i < arr.length; ++i) {
        for (int j = 0; j < arr.length; ++j) {
            ret[i][j] = arr[i][j];
        }
    }
    return ret;
}

public static void printBoard(int[][] board) {
    for (int i = 0; i < board.length; ++i) {
        for (int j = 0; j < board.length; ++j) {
            System.out.print(board[i][j]);
        }
        System.out.println();
    }
    System.out.println();
}

public static int solveBoard(int[][] board) {
    HashSetInteger[][] notes = new HashSetInteger[9][9];
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            notes[i][j] = new HashSetInteger();
            for (int k = 1; k <= 9; ++k) {
                notes[i][j].add(k);
            }
        }
    }

    boolean changed      = false;
    boolean allSet       = true;
    boolean secondChanges = true;
    do {
        changed = false;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == 0) {
                    for (int k = 0; k < 9; ++k) {
                        notes[i][j].remove(board[i][k]);
                        notes[i][j].remove(board[k][j]);
                        int startx = (i / 3) * 3;
                        int starty = (j / 3) * 3;
                        notes[i][j].remove(board[startx+(k%3)][starty+(k/3)]);
                    }
                    if (notes[i][j].size() == 1) {
                        for (Integer ger : notes[i][j]) {
                            board[i][j] = ger;
                        }
                        changed = true;
                    } else if (notes[i][j].size() == 0) {
                        return 0;
                    } else {
                        allSet = false;
                    }
                }
            }
        }
        secondChanges =  (!changed && !secondChanges);
    } while (changed || secondChanges);
    
    if (allSet) {
        return board[0][0]*100 + board[0][1]*10 + board[0][2];
    } else {
        int ret = 0;
        do {
        int[][] oldBoard = copyArray(board);
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == 0) {
                    if (notes[i][j].size() == 0) {
                        return 0;
                    }
                    for (Integer ger : notes[i][j]) {
                        board[i][j] = ger;
                        notes[i][j].remove(ger);
                        break;
                    }
                    i = 9;
                    j = 9;
                }
            }
        }
        ret   = solveBoard(board);
        board = oldBoard;
        } while (ret == 0);
        return ret;
    }
}

public static void main(String[] args) {
    int ans = 0;
    //we pass sudoku.txt through stdin
    //even though I guess it would be about as easy
    //to just past it to this scanner, huh?
    Scanner scan = new Scanner(System.in);
    scan.useDelimiter("");
    for (int i = 0; i < 50; ++i) {
        int[][] board = new int[9][9];
        scan.nextLine();
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                String s = scan.next();
                board[r][c] = Integer.parseInt(s);
            }
            scan.nextLine();
        }
        ans += solveBoard(board);
    }
    System.out.println(ans);
}

}