Given a 9x9 Sudoku grid with a valid solution.
I am trying to code a method that validates (in other words, checking for duplicates or out of range values) in the Sudoku 'box' (which in this case would be 3x3 and inside of the entire Sudoku puzzle). I want each index inside the 3x3 grid to check with other values and see if the values are equal, if they are then the 3x3 would be invalid. However, I notice (if I am not wrong) that the 'i' variable is incrementing in a weird way. 'i' is 0 when the for loop is first invoked, and then the next increment 'i' is also 0, and the last increment 'i' is 2. Not sure why it is going like that. Please let me know what I'm doing wrong
public boolean isValidBox(int row, int col) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
for (int l = 0; l < 3; l++) {
if (grid[row + i][col + j] == grid[row + k][col + l] && i != k && j != l) {
return false;
}
}
}
}
}
return true;
}
I'm expecting the code to make 81 checks, in other words, I am expecting the code in this line
if (grid[row + i][col + j] == grid[row + k][col + l] && i != k && j != l)
to run 81 times, but it's not doing that and I think it's running 243; 81*3 more times.
Thank you so much.
It looks like the code you have does not have any issues other than the logical problem pointed out by @Luatic. It seems likely that the code you use to measure the number of iterations may be to blame for the issue you are seeing.
If you are worried about the number of iterations and general performance, there are other options you can try though. For example, you could switch to an implementation that does not repeat comparisons such as this one which only performs 36 iterations. Fair warning though, I did not perform any benchmarks.
boolean isValidBox(int row, int col) {
for (int i = 0; i < 8; i++) {
int iRow = (i / 3) + row;
int iCol = (i % 3) + col;
for (int j = i + 1; j < 9; j++) {
int jRow = (j / 3) + row;
int jCol = (j % 3) + col;
if (grid[iRow][iCol] == grid[jRow][jCol]) {
return false;
}
}
}
return true;
}
An even better solution is to only check for duplicates when updating a cell so you only need to do a single pass to search for the cell's new value.