Project Euler 96 – Sudoku

Posted on December 9, 2013

Last updated on June 18, 2017

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();
    }   
  }
}
Euler 96 Solution
Markdown SHA1: 3c4edeeb138c14f965e3264928a4c76fd0e5dc04