Sudoku Solver Algorithm

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Step 1

Check row and column for duplicate number

Check row and column for duplicate number

public boolean checkColRow(int c, int r, int num) { for(int i=0; i < gridSize; i++) { if(board[c][i] == num || board[i][r] == num) return false; } return true; }

Step 2

Check $3 \times 3$ square for duplicate number

Check $3 \times 3$ square for duplicate number

public boolean checkColRow(int c, int r, int num) { for(int i=0; i < gridSize; i++) { if(board[c][i] == num || board[i][r] == num) return false; } return true; }

Step 3

Use backtrack to travel the tree

Use backtrack to travel the tree

public void solver(int k) { if(k == numEmpty) { printBoard(); } else { int c = array[k][0]; int r = array[k][1]; for(int i=1; i <= gridSize; i++) { if(checkColRow(c, r, i) && checkSquare(c, r, i)) { board[c][r] = i; solver(k+1); board[c][r] = 0; } } } }