I'm currently working on a little project of mine, a crossword Solver.
Given an Input of 64 characters, an algorithm displays them on a 8x8 board and then goes on to look if any of the word match.
So far I've written an algorithm that for each word loops through the letters on the board and checks if any of them are equal to the first character of the word. If that's the case, I call a helper function that returns all neighbours of the current character and proceeds checking if any of those neighbours are equal to the second character of the word, and so on.... So basically it is a breadth first search algorithm using a queue and pushing neighbours to that queue :)
So far this works perfectly, however I now realised, that once the algoorithm has matched the second character of a word, the helper funciton should only return the neighbour that has the same direction.
for example, if my board looks like this:
Y A T
C E V
B X S
and I need to look for the word 'YES', the algorithm gets a match at [0][0] and gets all the neightbours (in this case A,C,E). Then it checks if any of those match the second character of the word (here it is E). But now the algorithm should see that the word follows diagnoally and only return the diagonal neighbour (here S).
Do you know any elegant way of passing this information to the helper funciton without having to write thousands of if statements?
For better understanding, here is the code I've written so far:
https://jsfiddle.net/jakob_mayerhofer/84xrfuwL/7/
Of course, if you have any other suggestions how I could write the algorithm leaner/more efficently I'm open to all feedback.
Thanks for your help, appreciate it :)
I would not choose a BFS algorithm for this, because you already know the length of the word to look for. A BFS is what you would choose when you need to find the shortest path among alternatives, but here there are only 4 possible alternatives from a given starting point (north, south, east, west), and they all have equal length. In such a situation, you don't really need a graph-searching algorithm.
So I would change the inner part of your crossWordSolver, and use a loop over the 4 possible directions, and per direction, just scan in that direction immediately up to the length of the word.
Here is how that would look:
function crosswordSolver(words, grid) {
let directions = [[-1, 0], [0, -1], [1, 0], [0, 1]];
for (word of words) {
let found = false;
for (let i = 0; i < 8 && !found; i++) { // <-- extra exit condition
for (let j = 0; j < 8 && !found; j++) { // <-- ... also here.
if (grid[i][j] == word[0]) { // Simple check for 1st char
for (let [dx, dy] of directions) { // Four directions to scan.
found = true;
for (let k = 0, x = i, y = j; k < word.length; k++, x+=dx, y+=dy) {
if (x < 0 || y < 0 || x > 7 || y > 7 || word[k] !== grid[x][y]) {
found = false; // Out of bounds, or mismatch
break;
}
}
if (found) break;
}
}
}
}
if (found) checked.push(word);
}
console.log(checked);
}