Title: Sudoku Solver Source: leetcode.com
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
/* https://leetcode.com/problems/sudoku-solver/ */ class SudokuSolver { public void solveSudoku(char[][] board) { int N = board.length; solve(board, N); } private boolean isSafe(int row, int col, char c, char[][] sudoku, int N) { if(isSafeRow(row, col, c, sudoku, N) && isSafeCol(row, col, c, sudoku, N) && isSafeBox(row, col, c, sudoku, N)) return true; return false; } private boolean isSafeRow(int row, int col, char c, char[][] sudoku, int N) { //printSudoku(sudoku); //System.out.println("isSafeRow row: "+row+" col: "+col+" char: "+ c); for(int i=0;i<N;i++) { if(sudoku[row][i]==c) return false; } return true; } private boolean isSafeCol(int row, int col, char c, char[][] sudoku, int N) { //printSudoku(sudoku); //System.out.println("isSafeCol row: "+row+" col: "+col+" char: "+ c); for(int i=0;i<N;i++) { if(sudoku[i][col]==c) return false; } return true; } private boolean isSafeBox(int row, int col, char a, char[][] sudoku, int N) { //printSudoku(sudoku); //System.out.println("isSafeBox row: "+row+" col: "+col+" char: "+ a); int boxRow = row - row%3; int boxCol = col - col%3; for(int r=0;r<Math.sqrt(N);r++) { for(int c=0;c<Math.sqrt(N);c++) { if(sudoku[boxRow + r][boxCol +c] == a) return false; } } return true; } private boolean findUnassigned(int[] empty, char[][] sudoku, int N) { empty[0] = -1; empty[1] = -1; for(int r=0;r<N;r++) { for(int c=0;c<N;c++) { if(sudoku[r][c]=='.') { empty[0] = r; empty[1] = c; return true; } } } return false; } public boolean solve(char[][] sudoku, int N) { int[] empty = new int[2]; if(!findUnassigned(empty, sudoku, N)) return true; int row = empty[0]; int col = empty[1]; for(char i='1';i<='9';i++) { if(isSafe(row, col, i, sudoku, N)) { sudoku[row][col] = i; if(solve(sudoku, N)) return true; sudoku[row][col] = '.'; } } return false; } private void printSudoku(char[][] 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(); } } public static void main(String args[]) { String[] s = {"..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."}; char[][] board = new char[s.length][s.length]; for(int i=0;i<s.length;i++) { for(int j=0;j<s[i].length();j++) { board[i][j] = s[i].charAt(j); } } SudokuSolver ss = new SudokuSolver(); ss.solveSudoku(board); ss.printSudoku(board); } } |