Backtracking | Set 7 (Sudoku) | GeeksforGeeks
Given a partially filled 9×9 2D array ‘grid[9][9]‘, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.
Before assigning a number, we check whether it is safe to assign. We basically check that the same number is not present in current row, current column and current 3X3 subgrid. After checking for safety, we assign the number, and recursively check whether this assignment leads to a solution or not. If the assignment doesn’t lead to a solution, then we try next number for current empty cell. And if none of number (1 to 9) lead to solution, we return false.
http://www.cnblogs.com/TenosDoIt/p/3800485.html
http://bangbingsyb.blogspot.com/2014/11/leetcode-valid-sudoku-sudoku-solver.html
http://www.cnblogs.com/zhuli19901106/p/3574405.html
Total time complexity is O((n^2)!), but it would never appear that large. Space complexity is O(n^2)
The Dancing Links Algorithm seems to be a very exquisite way to solve Sudoku, but here it might be way too complicated for an interview question.
Java Solution from EPI
if (!isValidSudoku(A)) {
System.out.println("Initial configuration violates constraints.");
return false;
}
if (solveSudokuHelper(A, 0, 0)) {
for (int[] element : A) {
System.out.println(Arrays.toString(element));
}
return true;
} else {
System.out.println("No solution exists.");
return false;
}
}
private static boolean solveSudokuHelper(int[][] A, int i, int j) {
if (i == A.length) {
i = 0; // Starts a new row.
if (++j == A[i].length) {
return true; // Entire matrix has been filled without conflict.
}
}
// Skips nonempty entries.
if (A[i][j] != 0) {
return solveSudokuHelper(A, i + 1, j);
}
for (int val = 1; val <= A.length; ++val) {
// Note: practically, it's substantially quicker to check if entry val
// conflicts with any of the constraints if we add it at (i,j) before
// adding it, rather than adding it and then calling isValidSudoku.
// The reason is that we are starting with a valid configuration,
// and the only entry which can cause a problem is entryval at (i,j).
if (validToAdd(A, i, j, val)) {
A[i][j] = val;
if (solveSudokuHelper(A, i + 1, j)) {
return true;
}
}
}
A[i][j] = 0; // Undo assignment.
return false;
}
private static boolean validToAdd(int[][] A, int i, int j, int val) {
// Check row constraints.
for (int[] element : A) {
if (val == element[j]) {
return false;
}
}
// Check column constraints.
for (int k = 0; k < A.length; ++k) {
if (val == A[i][k]) {
return false;
}
}
// Check region constraints.
int regionSize = (int) Math.sqrt(A.length);
int I = i / regionSize, J = j / regionSize;
for (int a = 0; a < regionSize; ++a) {
for (int b = 0; b < regionSize; ++b) {
if (val == A[regionSize * I + a][regionSize * J + b]) {
return false;
}
}
}
return true;
}
todo:http://n00tc0d3r.blogspot.com/2013/06/sudoku-solver.html
// For each cell, populate an array of candidate numbers.
// Return the cell with least number of candidates.
private Pair<Integer, Integer> init(char[][] board, HashMap<Pair<Integer, Integer>, HashSet<Integer>> cand) {
// collect existing numbers
ArrayList<ArrayList<Integer>> numbersInRow = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> numbersInCol = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> numbersInBox = new ArrayList<ArrayList<Integer>>();
for (int i=0; i<9; ++i) {
ArrayList<Integer> row = new ArrayList<Integer>(); // row i
ArrayList<Integer> col = new ArrayList<Integer>(); // column i
for (int j=0; j<9; ++j) {
if (board[i][j] != '.') row.add(board[i][j]-'0');
if (board[j][i] != '.') col.add(board[j][i]-'0');
}
numbersInRow.add(row);
numbersInCol.add(col);
}
for (int i=0; i<9; i+=3) {
for (int j=0; j<9; j+=3) {
ArrayList<Integer> box = new ArrayList<Integer>(); // box i
for (int r=i; r<i+3; ++r) {
for (int c=j; c<j+3; ++c) {
if (board[r][c] != '.') box.add(board[r][c]-'0');
}
}
numbersInBox.add(box);
}
}
// initialize with all empty cells
int minSet = 10;
Pair<Integer, Integer> minCell = null;
for (int i=0; i<9; ++i) {
int boxR = (i/3) * 3;
for (int j=0; j<9; ++j) {
if (board[i][j] == '.') {
Pair<Integer, Integer> cell = new Pair<Integer, Integer>(i, j);
HashSet<Integer> set = new HashSet<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9));
set.removeAll(numbersInRow.get(i));
set.removeAll(numbersInCol.get(j));
set.removeAll(numbersInBox.get(boxR + j/3));
cand.put(cell, set);
if (set.size() < minSet) {
minCell = cell; minSet = set.size();
}
}
}
}
return minCell;
}
// Fill in the given cell with the given value and update candidate sets of same row/column/box.
// Return the cell with least number of candidates. If a conflict is detected, return the given cell.
private Pair<Integer, Integer> fillOneCell(char[][] board,
Pair<Integer, Integer> cell, int num,
ArrayList<Pair<Integer, Integer>> touched,
HashMap<Pair<Integer, Integer>, HashSet<Integer>> cand) {
board[cell.first][cell.second] = (char)('0' + num);
int minSet = 10;
Pair<Integer, Integer> minCell = null;
// resolve conflicts
for (Pair<Integer, Integer> c : cand.keySet()) {
if (c.first == cell.first || c.second == cell.second
|| ((c.first/3) == (cell.first/3) && (c.second/3) == (cell.second/3))) {
if (cand.get(c).remove(num)) {
touched.add(c);
if (cand.get(c).isEmpty()) return cell;
}
}
if (minCell == null || cand.get(c).size() < minSet) {
minCell = c; minSet = cand.get(c).size();
}
}
return minCell;
}
// Recursively solve a Sudoku.
// Return true if the current board is a valid Sudoku (could be partially filled).
private boolean solveSudokuHelper(char[][] board, Pair<Integer, Integer> cell,
HashMap<Pair<Integer, Integer>, HashSet<Integer>> cand) {
if (cand.isEmpty()) return true;
HashSet<Integer> set = cand.get(cell);
cand.remove(cell);
for (Integer num : set) { // try each candidate value
ArrayList<Pair<Integer, Integer>> touched = new ArrayList<Pair<Integer, Integer>>();
Pair<Integer, Integer> minCell = fillOneCell(board, cell, num, touched, cand);
// try next cell
if (!cell.equals(minCell) && solveSudokuHelper(board, minCell, cand)) return true;
// recover
for (Pair<Integer, Integer> cc : touched) {
cand.get(cc).add(num);
}
}
cand.put(cell, set);
return false;
}
public void solveSudoku(char[][] board) {
HashMap<Pair<Integer, Integer>, HashSet<Integer>> cand =
new HashMap<Pair<Integer, Integer>, HashSet<Integer>>();
Pair<Integer, Integer> cell = init(board, cand);
solveSudokuHelper(board, cell, cand);
}
Read full article from Backtracking | Set 7 (Sudoku) | GeeksforGeeks
Given a partially filled 9×9 2D array ‘grid[9][9]‘, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.
Before assigning a number, we check whether it is safe to assign. We basically check that the same number is not present in current row, current column and current 3X3 subgrid. After checking for safety, we assign the number, and recursively check whether this assignment leads to a solution or not. If the assignment doesn’t lead to a solution, then we try next number for current empty cell. And if none of number (1 to 9) lead to solution, we return false.
Find row, col of an unassigned cell
If there is none, return true
For digits from 1 to 9
a) If there is no conflict for digit at row,col
assign digit to row,col and recursively try fill in rest of grid
b) If recursion successful, return true
c) Else, remove digit and try another
If all digits have been tried and nothing worked, return false
/* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */bool SolveSudoku(int grid[N][N]){ int row, col; // If there is no unassigned location, we are done if (!FindUnassignedLocation(grid, row, col)) return true; // success! // consider digits 1 to 9 for (int num = 1; num <= 9; num++) { // if looks promising if (isSafe(grid, row, col, num)) { // make tentative assignment grid[row][col] = num; // return, if success, yay! if (SolveSudoku(grid)) return true; // failure, unmake & try again grid[row][col] = UNASSIGNED; } } return false; // this triggers backtracking}/* Searches the grid to find an entry that is still unassigned. If found, the reference parameters row, col will be set the location that is unassigned, and true is returned. If no unassigned entries remain, false is returned. */bool FindUnassignedLocation(int grid[N][N], int &row, int &col){ for (row = 0; row < N; row++) for (col = 0; col < N; col++) if (grid[row][col] == UNASSIGNED) return true; return false;}/* Returns a boolean which indicates whether any assigned entry in the specified row matches the given number. */bool UsedInRow(int grid[N][N], int row, int num){ for (int col = 0; col < N; col++) if (grid[row][col] == num) return true; return false;}/* Returns a boolean which indicates whether any assigned entry in the specified column matches the given number. */bool UsedInCol(int grid[N][N], int col, int num){ for (int row = 0; row < N; row++) if (grid[row][col] == num) return true; return false;}/* Returns a boolean which indicates whether any assigned entry within the specified 3x3 box matches the given number. */bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num){ for (int row = 0; row < 3; row++) for (int col = 0; col < 3; col++) if (grid[row+boxStartRow][col+boxStartCol] == num) return true; return false;}/* Returns a boolean which indicates whether it will be legal to assign num to the given row,col location. */bool isSafe(int grid[N][N], int row, int col, int num){ /* Check if 'num' is not already placed in current row, current column and current 3x3 box */ return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) && !UsedInBox(grid, row - row%3 , col - col%3, num);}http://www.cnblogs.com/TenosDoIt/p/3800485.html
void solveSudoku(vector<vector<char> > &board) { for(int i = 0; i < 9; i++) for(int j = 0; j < 9; j++) if(board[i][j] != '.') fill(i, j, board[i][j] - '0'); solver(board, 0); } bool solver(vector<vector<char> > &board, int index) {// 0 <= index <= 80，index表示接下来要填充第index个格子 if(index > 80)return true; int row = index / 9, col = index - 9*row; if(board[row][col] != '.') return solver(board, index+1); for(int val = '1'; val <= '9'; val++)//每个为填充的格子有9种可能的填充数字 { if(isValid(row, col, val-'0')) { board[row][col] = val; fill(row, col, val-'0'); if(solver(board, index+1))return true; clear(row, col, val-'0'); } } board[row][col] = '.';//注意别忘了恢复board状态 return false; } //判断在第row行col列填充数字val后，是否是合法的状态 bool isValid(int row, int col, int val) { if(rowValid[row][val] == 0 && columnValid[col][val] == 0 && subBoardValid[row/3*3+col/3][val] == 0) return true; return false; } //更新填充状态 void fill(int row, int col, int val) { rowValid[row][val] = 1; columnValid[col][val] = 1; subBoardValid[row/3*3+col/3][val] = 1; } //清除填充状态 void clear(int row, int col, int val) { rowValid[row][val] = 0; columnValid[col][val] = 0; subBoardValid[row/3*3+col/3][val] = 0; }private: int rowValid[9][10];//rowValid[i][j]表示第i行数字j是否已经使用 int columnValid[9][10];//columnValid[i][j]表示第i列数字j是否已经使用 int subBoardValid[9][10];//subBoardValid[i][j]表示第i个小格子内数字j是否已经使用};void solveSudoku(vector<vector<char> > &board) { if(board.size()<9 || board[0].size()<9) return; bool findSol = solSudoku(board, 0, 0); } bool solSudoku(vector<vector<char>> &board, int irow, int icol) { if(irow==9) return true; int irow2, icol2; if(icol==8) { irow2 = irow+1; icol2 = 0; } else { irow2 = irow; icol2 = icol+1; } if(board[irow][icol]!='.') { if(!isValid(board, irow, icol)) return false; return solSudoku(board, irow2, icol2); } for(int i=1; i<=9; i++) { board[irow][icol] = '0'+i; if(isValid(board, irow, icol) && solSudoku(board, irow2, icol2)) return true; } // reset grid board[irow][icol] = '.'; return false; } bool isValid(vector<vector<char>> &board, int irow, int icol) { char val = board[irow][icol]; if(val-'0'<1 || val-'0'>9) return false; // check row & col for(int i=0; i<9; i++) { if(board[irow][i]==val && i!=icol) return false; if(board[i][icol]==val && i!=irow) return false; } //check 3x3 box int irow0 = irow/3*3; int icol0 = icol/3*3; for(int i=irow0; i<irow0+3; i++) { for(int j=icol0; j<icol0+3; j++) { if(board[i][j]==val && (i!=irow || j!=icol)) return false; } } return true; }http://blog.csdn.net/linhuanmars/article/details/20748761
http://www.cnblogs.com/zhuli19901106/p/3574405.html
Total time complexity is O((n^2)!), but it would never appear that large. Space complexity is O(n^2)
The Dancing Links Algorithm seems to be a very exquisite way to solve Sudoku, but here it might be way too complicated for an interview question.
Java Solution from EPI
Implement a Sudoku solver SudokuSolve.java
public static boolean solveSudoku(int[][] A) {if (!isValidSudoku(A)) {
System.out.println("Initial configuration violates constraints.");
return false;
}
if (solveSudokuHelper(A, 0, 0)) {
for (int[] element : A) {
System.out.println(Arrays.toString(element));
}
return true;
} else {
System.out.println("No solution exists.");
return false;
}
}
private static boolean solveSudokuHelper(int[][] A, int i, int j) {
if (i == A.length) {
i = 0; // Starts a new row.
if (++j == A[i].length) {
return true; // Entire matrix has been filled without conflict.
}
}
// Skips nonempty entries.
if (A[i][j] != 0) {
return solveSudokuHelper(A, i + 1, j);
}
for (int val = 1; val <= A.length; ++val) {
// Note: practically, it's substantially quicker to check if entry val
// conflicts with any of the constraints if we add it at (i,j) before
// adding it, rather than adding it and then calling isValidSudoku.
// The reason is that we are starting with a valid configuration,
// and the only entry which can cause a problem is entryval at (i,j).
if (validToAdd(A, i, j, val)) {
A[i][j] = val;
if (solveSudokuHelper(A, i + 1, j)) {
return true;
}
}
}
A[i][j] = 0; // Undo assignment.
return false;
}
private static boolean validToAdd(int[][] A, int i, int j, int val) {
// Check row constraints.
for (int[] element : A) {
if (val == element[j]) {
return false;
}
}
// Check column constraints.
for (int k = 0; k < A.length; ++k) {
if (val == A[i][k]) {
return false;
}
}
// Check region constraints.
int regionSize = (int) Math.sqrt(A.length);
int I = i / regionSize, J = j / regionSize;
for (int a = 0; a < regionSize; ++a) {
for (int b = 0; b < regionSize; ++b) {
if (val == A[regionSize * I + a][regionSize * J + b]) {
return false;
}
}
}
return true;
}
todo:http://n00tc0d3r.blogspot.com/2013/06/sudoku-solver.html
// For each cell, populate an array of candidate numbers.
// Return the cell with least number of candidates.
private Pair<Integer, Integer> init(char[][] board, HashMap<Pair<Integer, Integer>, HashSet<Integer>> cand) {
// collect existing numbers
ArrayList<ArrayList<Integer>> numbersInRow = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> numbersInCol = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> numbersInBox = new ArrayList<ArrayList<Integer>>();
for (int i=0; i<9; ++i) {
ArrayList<Integer> row = new ArrayList<Integer>(); // row i
ArrayList<Integer> col = new ArrayList<Integer>(); // column i
for (int j=0; j<9; ++j) {
if (board[i][j] != '.') row.add(board[i][j]-'0');
if (board[j][i] != '.') col.add(board[j][i]-'0');
}
numbersInRow.add(row);
numbersInCol.add(col);
}
for (int i=0; i<9; i+=3) {
for (int j=0; j<9; j+=3) {
ArrayList<Integer> box = new ArrayList<Integer>(); // box i
for (int r=i; r<i+3; ++r) {
for (int c=j; c<j+3; ++c) {
if (board[r][c] != '.') box.add(board[r][c]-'0');
}
}
numbersInBox.add(box);
}
}
// initialize with all empty cells
int minSet = 10;
Pair<Integer, Integer> minCell = null;
for (int i=0; i<9; ++i) {
int boxR = (i/3) * 3;
for (int j=0; j<9; ++j) {
if (board[i][j] == '.') {
Pair<Integer, Integer> cell = new Pair<Integer, Integer>(i, j);
HashSet<Integer> set = new HashSet<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9));
set.removeAll(numbersInRow.get(i));
set.removeAll(numbersInCol.get(j));
set.removeAll(numbersInBox.get(boxR + j/3));
cand.put(cell, set);
if (set.size() < minSet) {
minCell = cell; minSet = set.size();
}
}
}
}
return minCell;
}
// Fill in the given cell with the given value and update candidate sets of same row/column/box.
// Return the cell with least number of candidates. If a conflict is detected, return the given cell.
private Pair<Integer, Integer> fillOneCell(char[][] board,
Pair<Integer, Integer> cell, int num,
ArrayList<Pair<Integer, Integer>> touched,
HashMap<Pair<Integer, Integer>, HashSet<Integer>> cand) {
board[cell.first][cell.second] = (char)('0' + num);
int minSet = 10;
Pair<Integer, Integer> minCell = null;
// resolve conflicts
for (Pair<Integer, Integer> c : cand.keySet()) {
if (c.first == cell.first || c.second == cell.second
|| ((c.first/3) == (cell.first/3) && (c.second/3) == (cell.second/3))) {
if (cand.get(c).remove(num)) {
touched.add(c);
if (cand.get(c).isEmpty()) return cell;
}
}
if (minCell == null || cand.get(c).size() < minSet) {
minCell = c; minSet = cand.get(c).size();
}
}
return minCell;
}
// Recursively solve a Sudoku.
// Return true if the current board is a valid Sudoku (could be partially filled).
private boolean solveSudokuHelper(char[][] board, Pair<Integer, Integer> cell,
HashMap<Pair<Integer, Integer>, HashSet<Integer>> cand) {
if (cand.isEmpty()) return true;
HashSet<Integer> set = cand.get(cell);
cand.remove(cell);
for (Integer num : set) { // try each candidate value
ArrayList<Pair<Integer, Integer>> touched = new ArrayList<Pair<Integer, Integer>>();
Pair<Integer, Integer> minCell = fillOneCell(board, cell, num, touched, cand);
// try next cell
if (!cell.equals(minCell) && solveSudokuHelper(board, minCell, cand)) return true;
// recover
for (Pair<Integer, Integer> cc : touched) {
cand.get(cc).add(num);
}
}
cand.put(cell, set);
return false;
}
public void solveSudoku(char[][] board) {
HashMap<Pair<Integer, Integer>, HashSet<Integer>> cand =
new HashMap<Pair<Integer, Integer>, HashSet<Integer>>();
Pair<Integer, Integer> cell = init(board, cand);
solveSudokuHelper(board, cell, cand);
}
Read full article from Backtracking | Set 7 (Sudoku) | GeeksforGeeks
