How to implement backtracking to check if all fields have been traversed

Question

I have been learning algorithms and trying to solve problems and now I have the following problem:

In a 4x4 matrix, and it contains fields with height. There is a start field with given height also the maximum height a field can have. To be able to traverse from on field to another the height of the current field must be higher or equal to the field we want to go. There are also unmarked fields with no height assigned to them, meaning we can change it. The goal is to traverse all the fields with given height by changing the height of the unmarked fields ?. For a solution to count as valid all given ? have to have an assigned height. I think this will need brute-forcing all the possible combinations of the ? fields.

Example:

2 2
xx*x
x1?1
x?1x
xxxx

The minimum height a field can have is 0. The first digit represents the height of the * and the second, the maximum height a field can have. So the * represents the start point and has height 2 (for this case we have 2 as maximum height), from there we need to go to the other fields with numbers, by changing the value of the ? fields. We need to find how many variations are valid. In this case there are : 6. Because the ? on 3rd row does not matter if it gets traversed or not so here are the solutions:

xx*x xx*x xx*x xx*x xx*x xx*x 
x121 x121 x121 x111 x111 x111
x21x x11x x01x x21x x11x x01x 
xxxx xxxx xxxx xxxx xxxx xxxx 

The nodes that matter have been traversed in both cases. We use Breadth First search to traverse all the nodes. The ? in the 3rd row is not traversed in some of the cases because this field is not in the group of the target fields and its height does not affect reaching any of the target fields.

• candied_orange: What is the "given height"? We don't have to traverse all fields?
• aurel: @CandiedOrange I added an example in the question
• candied_orange: So what is x? Is it ok to revisit marked fields? Are we required to find a minimal traversal path? Can we move diagonally?
• aurel: @CandiedOrange x are fields that you cant traverse
• candied_orange: Why not 3rd row ?={-1, 0, 1, 2, 3} The bounds you put on this don't seem to be explained by the rules. Please consider revising your original question. We shouldn't force others to read through all of these comments to understand the rules of this problem.

Answer 1

I think as you attempt to describe the situation more clearly, an approach will emerge.

Backtracking breaks down a search (tree) into paths, which are accepted, rejected, or neither. In the neither case, you go on to build a longer path; in the rejected case you "back up" to build further on the last non-rejected path.

To use backtracking, you have to identify your accept and reject functions. And of course, one has to also identify the function that appends to the path, lengthening it by one. This function will need some state to indicate which of the immediate next options it has already tried. This could be as simple as an integer indicating the child number last tried (or to try next). Because you'll need this state at each node in the path, you need a stack of some sort to maintain the current path (which also indicates what has already and hasn't yet been searched). The Wikipedia article shows use of recursion for that, but you could use an explicit stack instead.

So, the gist of it is that you need to decompose your problem into smaller pieces, and if backtracking is appropriate, these smaller pieces will distinctly involve being able to add one to the current path, being able to accept, and being able to reject the current path.

If the decomposition doesn't fit this, then you can use something else. For example, if there is no search tree, but rather a merely a search list, you wouldn't need to use backtracking (but you could if you insisted because a list is a form of tree).

Answer 2

The following should not be interpreted as a proper answer to your question. Instead it's an exception to your question.

You've been very good about answering questions in comments but even after trying to piece together the rules of your problem I don't see how you arrive at these 6 solutions. The remaining issues go beyond what I can explain in a comment field.

Here are the rules you've given (including your comments) as I understand them:

Given the following grid of heights:

xx*x
x1?1
x?1x
xxxx

Ignore x. Start at *. Assume the height of * is 2, the max (you assume 0 is the min but never state this as a rule). The goal is to visit every field that currently has a numerical height value. Visiting is done by moving from field to adjacent field, horizontally or vertically. You are only permitted to move if your new height would be less than or equal your old height. That is, moving follows these transition rules:

Transition rules based on height

enter image description here

Graphing tool: illuminations.nctm.org

Once per solution, a height, between the min and max (inclusive), may be chosen for each ? field. This choice does not obligate you to visit the ? field.

These are the game rules as I understand them. I don't fully understand how they produce these 6 solutions:

Solutions as given by OP (remember * = 2)

enter image description here

What I don't understand:

1. In solutions 1 to 3, if I visit ABC how do I ever get from C to E? When B is 2 there is no way to visit all the 1's.

2. Why I should bother giving F a value when I don't use it or care about visiting it. It only seems to blow up the number of solutions for no good reason.

3. Why * can't be a number 2. You could just state that the start is the 3rd column in the 1st row. It's going to be a pain deal with * in your code logic.

My solution

B = 1 and F is just left as ? since it's not needed.

enter image description here

We can see now that B thru E are strongly connected. Since they can be reached from the start (A) they may all be visited and marked. B doesn't need to be marked but it couldn't hurt.

Regarding backtracking:

Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.

For an example with this few unknown heights with min and max within 2 units of each other I'd just go with brute force.

That's likely not what you want to hear. If so, consider rewriting your question with more exacting and understandable rules. I suspect the answer to your question lies in formulating a "partial candidate solution". The "relatively quick test" is likely one of the algorithms mentioned in the strongly connected wiki page.

If you want to completely rewrite your question at this point I wouldn't blame you. Feel free to invalidate this answer if you can write a better question. I'll just delete/edit it and try again. At this point this is the best I can do. I hope it at least helps you improve your question.

• aurel: Very good representation, the reason that I give value to the second ? is because that is valid configuration of the matrix. And that is what I need to find. For solutions you basically do a BFS and see if the necessary fields are visited. Thanks for trying to understand my problem and explain it better, I found a solution I think, by searching all possible permutations of the ? given and have a counter for the valid ones.
• candied_orange: Leaving the second ? as ? is also a valid configuration of the matrix. You're missing a transition rule: no transition. If no transition is valid that's a good stand in for "doesn't matter how connected this node is, any height would do". Remember the goal is simply to mark CDE. That's only #2 of what I don't understand. How about #1 and #3?
• aurel: We have to assign a value to ?. Number #3 is because the matrix will be inputted so we know where the start is. #1 we use BFS, then we can do the transition. Also you are right about using brute force
• candied_orange: Yes you need some way to know where the start is. You also need some way to know what the starts height is. If you're going to put one of those two bits of information outside of the matrix, putting the height out seems a very odd choice since the rest of the matrix is about height.
• candied_orange: I'm taking BFS as breadth first search. I'm now taking that to mean you are free to effectively return to the start any time you like. I'd like to note that this means the only invalid solutions are those where B = 0. I'm disappointed that you're not updating the question to clarify these rules.