This question requires us to solve Sudoku puzzles. We can use a backtracking DFS search to try all the possibilities.
1 Java Solution
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();
}
}
}