Empty cells are indicated by the character
'.'
.You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
Solution
public class Solution { public void solveSudoku(char[][] board) { solveSudoku(board, 0, 0); } public boolean solveSudoku(char[][] board, int row, int col) { if (row == 9) return true; int nextRow = col == 8 ? row+1 : row; int nextCol = col == 8 ? 0 : col+1; if (board[row][col] !='.') return solveSudoku(board, nextRow, nextCol); for (char c='1'; c<='9'; c++) { if (canPut(board, c, row, col)) { board[row][col] = c; if (solveSudoku(board, nextRow, nextCol)) return true; board[row][col] = '.'; } } return false; } public boolean canPut(char[][] board, char c, int row, int col) { for(int i=0; i<9; i++) { if(board[row][i]==c) return false; if(board[i][col]==c) return false; } int startRowGroup = (row/3)*3; int startColGroup = (col/3)*3; for(int i=startRowGroup; i<startRowGroup+3; i++) { for(int j=startColGroup; j<startColGroup+3; j++) if(board[i][j]==c) return false; } return true; } }
No comments :
Post a Comment