I have written a program for an exercise that generates numOfValidBoardsToCreate Sudoku boards with emptyCellsPerBoard cells with 0s (fills the rest with random numbers) and then solves them. If a generated board isn't valid or solvable it tries to create another one until it gets it. Now let's say we request just one board with 75 empty cells and its solution for the sake of simplicity.
The solve() method checks if a board is solvable and if so it solves it and returns true. Now, since when i check for each board's validity in the if statement of the for loop using isSolvableBoard() which in turn calls solve(), i don't want to solve the original board since i'm going to need to display the original unsolved one and then the solution. So i decided to use sudokuBoard.clone() to make a copy of the original one and use that for the check and disregard it since it's going to be solved after the condition is evaluated. I'd expect that the original sudokuBoard inside the if() statement wouldn't be solved when i print it the first time but the output is the solved version. What am i missing here?
public static void main(String[] args) {
BacktrackingAlgorithm solver = new BacktrackingAlgorithm();
// Get the required input from the user
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the number of empty cells that the board should have:");
int emptyCellsPerBoard = scanner.nextInt();
System.out.println("Enter how many boards the app should create and solve:");
int numOfValidBoardsToCreate = scanner.nextInt();
// extra data to keep track of for printing purposes
int numOfInvalidBoards = 0;
int numOfUnsolvableBoards = 0;
// finding the time before the operation is executed
long start = System.currentTimeMillis();
int[][] sudokuBoard;
int[][] copyOfBoard;
for (int i = 1; i <= numOfValidBoardsToCreate; i++) {
sudokuBoard = solver.generateSudokuBoard(emptyCellsPerBoard);
// Create a copy of the board to pass to isSolvableBoard to test the condition without altering the board
copyOfBoard = sudokuBoard.clone();
if (solver.isSolvableBoard(copyOfBoard)) {
System.out.println("Board #"+i);
solver.printBoard(sudokuBoard);
System.out.println("Solution of board #"+i);
solver.solve(sudokuBoard);
solver.printBoard(sudokuBoard);
} else {
numOfUnsolvableBoards++;
numOfInvalidBoards++;
i--; // run the loop again if we haven't reached the end
}
}
// finding the time after the operation is executed
long end = System.currentTimeMillis();
//finding the time difference and converting it into seconds
float sec = (end - start) / 1000F;
// Print final message
System.out.println("Empty Cells per board: " + emptyCellsPerBoard + "\nValid boards created: " + numOfValidBoardsToCreate + "\nInvalid boards created: "
+ numOfInvalidBoards + "\nUnsolvable boards created: " + numOfUnsolvableBoards + "\nElapsed time: " + sec + " seconds");
}
}
boolean solve(int[][] board) {
for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
if (board[row][column] == NO_VALUE) {
for (int k = MIN_VALUE; k <= MAX_VALUE; k++) {
board[row][column] = k;
if (isValid(board, row, column) && solve(board)) {
return true;
}
board[row][column] = NO_VALUE;
}
return false;
}
}
}
return true;
}
/**
* Checks if a Sudoku board is valid and solvable.
*
* @param board The given board
* @return True if it is or false otherwise.
*/
boolean isSolvableBoard(int[][] board) {
return isValidBoard(board) && solve(board);
}
/**
* Checks if the given sudoku board is valid.
*
* @param brd The 9x9 board
* @return True if it's valid or false otherwise.
*/
private boolean isValidBoard(int[][] brd) {
for (int i = BOARD_START_INDEX; i < BOARD_SIZE; i++) {
for (int j = BOARD_START_INDEX; j < BOARD_SIZE; j++) {
try {
if (!isValid(brd, i, j)) return false;
} catch (ArrayIndexOutOfBoundsException e) { // if a given cell has a value > 9, an exception is thrown, so handle it
return false;
}
}
}
return true;
}
