I have a problem with implementing the following task.
A square matrix has eleven letters missing, which you have to replace.
Every row, column contain all the letters in the word "BRAVE".
The problem is when I try to run this code it seems that there is infinite recursion, the program is never ending.
I have been debugging for two days, Still I cannot find what is wrong.
public class Crossword {
static Character[] letters = new Character[]{'B', 'R', 'A', 'V', 'E'};
static boolean isFilled(char[][] matrix) {
Set<Character> lettersSet = new HashSet<>(Arrays.asList(letters));
// Check rows and columns simultaneously
for (int i = 0; i < matrix.length; i++) {
Set<Character> rowLetters = new HashSet<>();
Set<Character> colLetters = new HashSet<>();
for (int j = 0; j < matrix.length; j++) {
rowLetters.add(matrix[i][j]);
colLetters.add(matrix[j][i]);
}
if (!rowLetters.containsAll(lettersSet) || !colLetters.containsAll(lettersSet)) {
return false;
}
}
return true;
}
static boolean containsLetter(char[] row, char symbol) {
for (char c : row) {
if (c == symbol) {
return true;
}
}
return false;
}
static void fillMatrixBruteForce(char[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
if (matrix[i][j] == ' ') {
for (int k = 0; k < letters.length; k++) {
if (!containsLetter(matrix[i], letters[k])) {
matrix[i][j] = letters[k];
if (isFilled(matrix)) {
return;
} else {
fillMatrixBruteForce(matrix);
}
}
}
matrix[i][j] = ' ';
}
}
}
}
static void print(char[][] matrix) {
Arrays.stream(matrix).forEach(
System.out::println
);
}
public static void main(String[] args) {
char[][] matrix = {
{'B', 'R', 'A', 'V', 'E'},
{' ', 'E', 'B', 'R', ' '},
{' ', ' ', 'V', ' ', 'B'},
{' ', 'B', 'R', ' ', ' '},
{' ', ' ', 'E', 'B', ' '}
};
print(matrix);
fillMatrixBruteForce(matrix);
print(matrix);
There are two issues with the code.
The first is a bug in the recursion that results in the second-to-last blank cell never getting filled in.
if (isFilled(matrix)) {
return;
} else {
fillMatrixBruteForce(matrix);
}
In the first case, we check if we just placed the final letter. If we did, we return. That part is fine.
In the second case, we call ourselves recursively to see if this guess leads to a solution. However, regardless of the outcome, we act as if we failed and undo our guess.
To fix this, we also check whether the recursion succeeded, in which case we return:
if (isFilled(matrix)) {
return;
} else {
fillMatrixBruteForce(matrix);
if (isFilled(matrix)) {
return;
}
}
(Alternatively, fillMatrixBruteForce can return either true or false to signal whether it succeeded or gave up. This means we won't have to check isFilled a second time.)
The second issue is the performance. The algorithm, as written, is very slow. Luckily, there is a simple tweak to massively speed it up.
For context, there are 11 open cells, each capable of containing one of five letters. That's 48,828,125 different possibilities to check. You really don't want to force your computer to recursively check all of those, meaning that rapidly giving up on impossible values is crucial.
You already do this somewhat with your containsLetter method. However, that only checks if a given row contains the letter. This means that a LOT of obviously impossible combinations slip through the cracks and are fully brute-forced. By adding a second method, columnContainsLetter and checking whether the letter exists in either the current row or the column (or both), that MASSIVELY cuts down on the number of possibilities we're forced to check and makes the algorithm run in mere seconds on my computer.