This question requires us to solve Sudoku puzzles. We can use a backtracking DFS search to try all the possibilities.
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class Euler96 { int sum = 0; public void solveSudoku(int[][] board) { solve(board, 0); } private boolean solve(int[][] board, int ind){ if(ind == 81){ sum += (100*board[0][0] + 10*board[0][1] + board[0][2]); return true; // solved } int row = ind / 9; int col = ind % 9; // Advance forward on cells that are prefilled if(board[row][col] != 0) return solve(board, ind+1); else{ // we are positioned on something we need to fill in. // Try all possibilities for(int i = 1; i <= 9; i++){ if(consistent(board, row, col, i)){ board[row][col] = i; if(solve(board, ind+1)) return true; board[row][col] = 0; // unmake move } } } // no solution return false; } // Check whether putting "c" into index "ind" leaves the board in a consistent state public boolean consistent(int[][] board, int row, int col, int c) { // check columns/rows for(int i = 0; i < 9; i++){ if(board[row][i] == c) return false; if(board[i][col] == c) return false; } int rowStart = row - row % 3; int colStart = col - col % 3; for(int m = 0; m < 3; m++){ for(int k = 0; k < 3; k++){ if(board[rowStart + k][colStart + m] == c) return false; } } return true; } public static void main(String[] args) { Euler96 e = new Euler96(); try { Scanner s = new Scanner(new File("sauce/sudoku.txt")); for(int i = 0; i < 50; i++){ s.nextLine(); int[][] result = new int[9][9]; for(int j = 0; j < 9; j++){ String n = s.nextLine(); char[] nn = n.toCharArray(); for(int k = 0; k < 9; k++){ result[j][k] = nn[k] - '0'; } } e.solveSudoku(result); } System.out.println(e.sum); } catch (FileNotFoundException e1) { e1.printStackTrace(); } } }