I have a 4x4 grid and 10 letters long word. I am trying to create an algorithm which will populate letters to the string[,] matrix but not randomly all over the matrix but with the specific order from the first letter to the last one.
Currently, I don’t have a correct solution because somehow I create a dead end and there is no way out for the next letter. I encounter this situation:
The first letter started at 3,2 went to 2,2 went to 2,3 and my algorithm sees 3,3 as a normal option to select, how can avoid that and change the direction to 1,3 or 1,2 for example.
So I how to improve the algorithm to check is the next position good enough to go to?
Just speaking hypothetically here…
evaluate your position to determine if it can complete all 10 letters by going on a certain path.
If it cannot, in the case of 3,3 try your other option… (in theory, if that one failed, you’d have to retry from 2,2 I guess). Makes sense in my head 
That is an interesting question.
And I’ll say this, it’s not trivial.
I’m not sure what your skill level is either.
This question is similar to a AI pathfinding question, but instead of ‘find shortest path to target’, you want ‘find path of length X’.
So you’re going to want to dive into some graph theory. I’d start with some sort of graph search and building paths from a random starting point. Throwing out paths that end to short.
From there you can go with the first path of length X (10) that you find… but that might create some predictability in your algorithm. So it might be better to generate several, and then select one randomly from that set.
Of course you’re first going to need to implement your graphs (not just the storage container, your array, but how to access it as a graph). Here is some classes I’ve written in the past for graph searching:
(you’ll notice there are Dijkstra and A* algorithms in there… I obvsly created these for AI pathfinding, but the underlying graph theory stuff is there)
And here’s some stuff on graphs themselves:
…
Now if this happens to be going over your head. It’s not actually super complicated, it’s just not trivial.
@methos5k describes it pretty basically. You’re just repeatedly calculating paths, and throwing out those that fail.
So… don’t fill your grid array as you calculate. Instead hypothetically fill your grid, by describing paths. Throw out as they fail. And once you have a successful one… then go back and fill your grid appropriately using that path.
Thank you very much guys, I will give it a try now!
Cool, good luck
I’ve never tried to do it … that’s just what came to mind looking at his situation - for the record heh.
So, how I resolved it, TRY-FAIL-TRY-PASS
I haven’t improved the algorithm too much, just implemented try-catch block and some checks if the path was successfully found or not. If not repeat the search again.
Regards