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