# Is calculate each line & column & square runs FASTER than using HashSet?

• I wrote two codes to sovle this problem.

• The first way is using 27 Sets to save the available digits of
each line, each column and each square. 420ms used.
• The second way is using only ONE set to save the available
digits of the current line that we are traversing now, and calculate the column and the square. 340ms used.

I thought the first way should runs faster than the second way, but the result shows that the second way runs faster.

Here are the codes.

First one: 420ms

``````public void solveSudoku(char[][] board) {
init(board);
fill(board,0,0);
}
private HashSet<Character> V[]=new HashSet[9];
private HashSet<Character> H[]=new HashSet[9];
private HashSet<Character> S[]=new HashSet[9];
private boolean fill(char[][] board,int line,int column) {
if (line==9){
return true;
}
if (board[line][column]!='.'){
return fill(board,line+(column+1)/9,(column+1)%9);
}
HashSet<Character> availableSet=findAvailable(line,column);
for (char c:availableSet){
board[line][column]=c;
V[line].remove(c);
H[column].remove(c);
S[(line/3)*3+column/3].remove(c);
if (fill(board,line+(column+1)/9,(column+1)%9)){
return true;
}
board[line][column]='.';
}
return false;
}
private HashSet<Character> findAvailable(int line,int column){
HashSet<Character> availableSet=new HashSet<Character>();
for (char c:V[line]){
}
availableSet.retainAll(H[column]);
availableSet.retainAll(S[(line/3)*3+column/3]);
return availableSet;
}
private void init(char[][] board){
for (int i=0;i<9;i++){
}
for (int i=0;i<9;i++){
for (int j=0;j<9;j++){
V[i].remove(board[i][j]);
H[j].remove(board[i][j]);
S[(i/3)*3+(j/3)].remove(board[i][j]);
}
}
}
``````

Second one: 340ms

``````public class Solution {
public void solveSudoku(char[][] board) {
fill(board,0,0,new HashSet<Character>());
}
private boolean fill(char[][] board,int line,int column,HashSet<Character> availableDigit){
if (line==9)
return true;
if (column==0){
for (int iterator=0;iterator<9;iterator++){
if (board[line][iterator]!='.'){
availableDigit.remove(board[line][iterator]);
}
}
}
if (board[line][column]!='.'){
//availableDigit.remove(board[line][column]);
boolean filled=fill(board,line+(column+1)/9,(column+1)%9,availableDigit);
if (filled){
return true;
}
else return false;
}
HashSet<Character> newDigits=realAvailable(availableDigit,board,line,column);
for (char c:newDigits){
board[line][column]=c;
availableDigit.remove(c);
boolean filled=fill(board,line+(column+1)/9,(column+1)%9,availableDigit);
if (filled){
return true;
}
board[line][column]='.';
}
return false;
}
private HashSet<Character> realAvailable(HashSet<Character> available,char[][] board,int line,int column){
HashSet<Character> newDigits=new HashSet<Character>();
for (char c:available){
}
for (int i=0;i<9;i++){
newDigits.remove(board[i][column]);
}
int dockLine=(line/3)*3;
int dockColumn=(column/3)*3;
for (int i=dockLine;i<dockLine+3;i++){
for (int j=dockColumn;j<dockColumn+3;j++){
if (board[i][j]!='.'){
newDigits.remove(board[i][j]);
}
}
}
return newDigits;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.