Snakes and Ladders
Introduction Graph problems pervade computer science, and algorithms to working with them are fundamental to the field. Hundreds of interesting computational problems are couched in terms of graphs. Today let’s discuss graph algorithms. In fact, I like this problem so much because it reminds me of my childhood. We were playing this game during our school holidays with our friends and it was fun. Let us get into the details next. Problem Statement You are given an $n \times n$ integer matrix board where the cells are labeled from $1$ to $n^2$ in a Boustrophedon style starting from the bottom left of the board (i.e. $board[n - 1][0]$) and alternating direction each row. You start on square $1$ of the board. In each move, starting from square curr, do the following: Choose a destination square next with a label in the range $[curr + 1, min(curr + 6, n^2)]$ This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the siz...