Path finding Algorithms, Stuck on basics

Question

This is a basic college puzzle question i have which i though i will nail, but when it comes to implementing it i got stuck right on the get go.

Background: a 4 digit path finding algorithm, so given for example a target number 1001 and target number 1040, find path using BFs,DFs...Etc.

Allowed moves: add or subtract 1 from any of the 4 digits in any order, you cannot add to 9, or subtract from 0. You cannot add or subtract from the same digit twice i.e. to get from 1000 to 3000, you cannot do 2000 ->3000 as you’ll be adding 1 twice to the first digit. So you'll have to do 2000->2100->3100->3000.

Where I am Stuck: I just cannot figure out how i will represent the problem programmatically, never mind the algorithms, but how i will represent 1001 and move towards 1004 .What data structure? How will I identify the neighbours?

Can someone please push me towards the right direction?

Answer 1

If I understand correctly, you're looking for a way to represent your problem. Perhaps you're having difficulties to find it, because the problem uses a 4 digit number. Try to reduce the dimensions, and consider the same problem with 2 digits numbers (see also this other answer). Suppose you want to move from 10 to 30 using the problem's rules. Now that you have two dimensions, you may easily represent your problem on a 10x10 matrix (each digit can have 10 different values):

:

In the picture above S is your source position (10), and T is your target position (30). Now you can apply the rules of the problem. I don't know what you want to find: how many paths? just a path? the shortest path?

Anyway, a sketch of algorithm for handling moves is:

• if you look at T you see that according to the rules of your problem, the only possible neighbours from which you can reach (30) are (20), (31), and (40).

• now, let's assume you choose (20), then the only possible neighbour from which you can reach (20) is (21).

• now, you're forced to choose (21), and the only possible neighbours from which you can reach (21) are (11) and (31).

• finally, if you choose (11), then the only possible neighbours from which you can reach (11) are (10) and (12) ... and (10) is your source S, so you're done.

This is just a sketch for the algorithm (it doesn't say anything on how to choose from the list of possible neighbours), but I hope it gives you an idea.

Finally, when you've solved the problem in the two-dimensional space, you can extend it to a three-dimensional space, and to a four-dimensional space (your original problem), where you have a 10x10x10x10 matrix. Each dimension has always 10 slots/positions.

I hope this helps.