Snake and Ladder with Graphs
Recently I was looking for some coding problems. One problem caught my eye and after referring to the solution I was like “Oh, I would have never interpreted like that.”
The problem is :
In a Snake and Ladder game you are in control of the outcome of the die throws. Now you have to reach a destination cell/box from the starting cell with minimum number of die throws in a given Snake and Ladder board.
So, I immediately took my pen and paper and got the answer for one such example. But that was not interesting .Anyone could have done that. The interesting part was the actual solution which I am going to share here.
So take a cells/boxes numbered 1,2,3….n as vertices of a Graph.
- For any vertex ‘v’ add an edge to v+1,v+2,v+3,v+4,v+5,v+6 as we can reach any of these 6 vertices in a die throw.
- If a vertex ‘v’ contains a ladder or a snake that takes us to the position ,say ‘u’ then add an edge from v->u instead of adding the edges between v->(v+1),(v->v+2) and so on.
Now, we have to find the number of edges in the shortest path or shortest route between the two vertices in this graph to find the minimum number of die throws required to reach the destination cell from the source.
This is simple but I felt interesting about the question. Even after playing Snake and Ladder 100 times ,no such question like the one stated above came to my mind.
The same with Sudoku, Eight queens problem and so on .These are very simple problems. Solving these however may not have any real life applications. Who would want to learn to solve N-Queens problem and many other similar ones after getting placed?
But I think with this starts the practice of breaking down many complex problems down to logic ,down to bits and then developing an algorithm to solve the problem. One might face many technical errors in Web/App development, Machine Learning, Data science. But facing such coding problems and attempting to solving it definitely would improve the perception on our real world problems.
Above all ,besides helping in cracking interviews ,these coding exercises/math sharpens our brain to approach the problem(technical) from many possible approaches.
Do you agree? Please share your views on this!!!
Also share similar questions where an actual Puzzle is reduced to a DS problem
