{"id":822,"date":"2021-01-21T09:34:17","date_gmt":"2021-01-21T17:34:17","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/azure-sql\/?p=822"},"modified":"2021-01-23T18:11:25","modified_gmt":"2021-01-24T02:11:25","slug":"solving-the-river-crossing-problem-with-sql-graph","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/azure-sql\/solving-the-river-crossing-problem-with-sql-graph\/","title":{"rendered":"Solving the River Crossing problem with SQL Graph"},"content":{"rendered":"

Are you are familiar with the classic \u201criver crossing<\/a>\u201d problem? If not, an easy 4 minutes introduction using Wildebeest and Lions as the actors in the problem, is presented in this TED-Ed talk<\/a>. If you observe carefully, the video briefly mentions using an enumeration approach to list all the possible transitions, and for each transition, the end state. It so happens that this is the classic algorithmic approach as well to solve such problems \u2013 to create a graph of all possible states (represented by vertices \/ nodes in the graph) and the transitions (represented by edges) which result into those states.\u00a0If you search online, there are plenty of references showing you how to use Breadth-First-Search (BFS) to find the shortest path to solve the problem. David Kopec\u2019s Classic Computer Science Problems<\/a> books also present implementations of this problem in Python and other languages.<\/p>\n

Let\u2019s see if we can solve this classic problem, using T-SQL and the graph capabilities<\/a> in Azure SQL \/ SQL Server!<\/p>\n

Governing Rules<\/h2>\n

Let\u2019s present the main \u201crules\u201d of this problem, as presented in the TED talk:<\/p>\n

    \n
  1. There are 3 wildebeest<\/a> and 3 lions<\/a>, all located on one bank (for completeness, we have the West bank, and the East bank) of a river. They are trying to cross the other river bank.<\/li>\n
  2. As it turns out, wildebeest are a natural prey for the lions. Therefore, there is a \u201crule\u201d which states that if the number of wildebeest either equal, or outnumber the number of lions, on the same bank of the river, they are safe. In our context, we will call this a \u201csafe\u201d state.<\/li>\n
  3. Conversely, If the number of wildebeest are lesser than the number of lions, they are unsafe. In our context, we will refer to this as an \u201cunsafe\u201d or \u201cdisallowed\u201d state, as we don\u2019t want the wildebeest to come to harm!<\/li>\n
  4. Let\u2019s also imagine, that these animals know how to use a raft, to cross the river \ud83d\ude0a However, the raft can only take 2 animals at any time, and obviously, the raft is not \u201cautonomous\u201d, and needs an animal or 2 animals on board to move from one bank of the river to the other.<\/li>\n
  5. At any given point in time, rules 2 and 3 must continuously be applied, even when 2 animals are on the raft!<\/li>\n<\/ol>\n

    Notation for states (nodes \/ vertices)<\/h2>\n

    We will represent the current \u201cstate\u201d of this situation by using simple notations:<\/p>\n