import java.io.File; import java.io.FileNotFoundException; import java.util.Arrays; import java.util.Scanner; /** * This is a Sudoku Solver that solves a partial Sudoku Board using * recursion. The Sudoku solver fills a N×N (N=9 by default) grid * with digits so that each column, each row, and each of the Size * ×Size (N=Size × Size while Size =3 by default) subgrids contains * all of the digits from 1 to 9. *

* You need to implement the solve(SudokuBoard b, int current) method * using recursion. Everything else is given to you. *

*

* Don't change other given methods/fields. You can add some private * helper methods but you may not add new public methods or fields. *

*/ public class Sudoku { public static int noSolves = 0; public static int size; @SuppressWarnings("resource") public static void main(String[] args) throws FileNotFoundException { // Initialize board Scanner sc = new Scanner(new File("sudoku.in")); boolean more = true; while (more) { int n = sc.nextInt(); size = n * n; int[][] initial = new int[size][size]; for (int cell = 0; cell < size * size; cell++) { initial[cell / size][cell % size] = sc.nextInt(); } System.out.println(initial.length); solve(initial); more = sc.hasNextInt(); if (more) { System.out.println(); // Print blank line between test cases } } } public static void solve(int[][] initial) { if (size == 1) { System.out.println(1); return; } SudokuBoardSoln brd = new SudokuBoardSoln(size, initial); if (solve(brd, brd.nextEmpty(-1))) { brd.print(); } else { System.out.println("NO SOLUTION"); } } public static boolean solve(SudokuBoardSoln b, int current) { noSolves++; // For debug // current increases from 0 to size^2 - 1 -- first along a // row, then downwards. // IF the current placement is at square size^2, we are done. // ELSE // LOOP try out all 'size' numbers in the current square. // IF any number is safe to place there // Place it. // Call solve with the next square without an initial value. // IF above returns TRUE // RETURN TRUE. // ELSE // Remove the placement, (and try the next possible digit) // END LOOP // RETURN false (if we fall out of the LOOP without returning true, we have exhausted 1 - size) if(current == size * size) { return true; } for(int i=1; i < size + 1; ++i) { // System.out.println("Checking: " + i + " at " + current%size + " " + current/size); if(b.isSafe(i, current)){ b.set(i, current); if(solve(b, b.nextEmpty(current))) { return true; } b.remove(i, current); } } return false; } } class SudokuBoardSoln { int[][] board; boolean[][] initial; int size; int N; public SudokuBoardSoln(int size) { this.size = size; N = (int) (Math.sqrt(size) + 1e-3); board = new int[size][size]; } public SudokuBoardSoln(int size, int[][] starting) { this(size); initial = new boolean[size][size]; // Is a square is // initialized? Iff not, // program may change its // value. for (int r = 0; r < size; r++) { for (int c = 0; c < size; c++) { if (starting[r][c] != 0) { initial[r][c] = true; } } } for (int r = 0; r < size; r++) { board[r] = Arrays.copyOf(starting[r], size); } } public void set(int a, int n) { board[n / size][n % size] = a; } public void remove(int a, int n) { set(0, n); } /* * Given a square, find the next one that was not initialized. */ public int nextEmpty(int n) { n++; if (n == size * size) { return n; } int row = n / size; int col = n % size; while (initial[row][col]) { n++; if (n == size * size) { return n; } row = n / size; col = n % size; } return n; } /* * Whether safe to place number 'a' in space 'n'. */ public boolean isSafe(int a, int n) { int row = n / size; int col = n % size; // If putting 'a' at location 'n' causes duplicate // number at its row, return false for (int i = 0; i < size; ++i) { if (board[row][i] == a) { return false; } } // If putting 'a' at location 'n' causes duplicate // number at its column, return false for (int i = 0; i < size; ++i) { if (board[i][col] == a) { return false; } } // If putting 'a' at location 'n' causes duplicate // number at its inner 3*3 (any N by N) square, return false int r = row / N; int c = col / N; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (board[r*N + i][c*N + j] == a) { return false; } } } // Hint: If there is a duplicate number, it means that one // number is missing (e.g. If we have two 1s in range of // [1..9], it means one of the other numbers is missing as we // can have at most 9 empty cells). return true; } public void print() { for (int r = 0; r < size; r++) { String blank = ""; for (int c = 0; c < size; c++) { if (board[r][c] == 0) { System.out.print(blank + "*"); } else { System.out.print(blank + board[r][c]); } blank = " "; } System.out.println(); } } }