Some mazes have a very large number of solutions. In this case, we may encounter some problems of memory capacity. We will consider mazes whose number of solutions remain reasonable. Furthermore, we will avoid the solutions that pass repeatedly through the same cell in order not to have an infinite number of solutions.

Representation of mazes

We can represent a maze by a two-dimensional array of the integers with the following conventions,

We set the table size to 10x10 in the source code, but this size can be changed or even become variable. The cells are located by their coordinates in a Windows coordinate system; i.e,. by pairs of the form column/line.

mazes

Algorithm

We will build the paths, starting from the entry point of the Maze and going in all the possible directions.

Actually a path extending from one point to another will be represented by a list of X-axis values and a list of Y-axis values of the points that make up the path.

The idea is to replace a path by all the paths obtained from it, by adding an unoccupied box not already visited at the end.

It initializes a list with a path containing a single point of departure.

It traverses the list of paths and for each path,

The program

  1. bool alreadyVisited(List < int > pX, List < int > pY, int x, int y)
  2. {
  3. bool notVisited = true;
  4. int n = pX.Count - 1;
  5. while (n >= 0 && notVisited)
  6. {
  7. if (pX[n] == x)
  8. if (pY[n] == y)
  9. {
  10. notVisited = false;
  11. }
  12. n--;
  13. }
  14. return !notVisited;
  15. }
  1. public void SolveMaze()
  2. {
  3. List < List < int >> pathXList = new List < List < int >> ();
  4. List < List < int >> pathYList = new List < List < int >> ();
  5. List < int > pathX = new List < int >
  6. {
  7. startX
  8. };
  9. List < int > pathY = new List < int >
  10. {
  11. startY
  12. };
  13. pathXList.Add(pathX);
  14. pathYList.Add(pathY);
  16. while (pathXList.Count > 0)
  17. {
  18. int pathNumber = pathXList.Count;
  19. while (pathNumber > 0)
  20. {
  21. pathX = pathXList[0];
  22. pathY = pathYList[0];
  23. int n = pathX.Count - 1;
  24. int x = pathX[n];
  25. int y = pathY[n];
  26. if (x == endX && y == endY)
  27. {
  28. completePathX.Add(pathX);
  29. completePathY.Add(pathY);
  30. pathXList.RemoveAt(0);
  31. pathYList.RemoveAt(0);
  32. } else
  33. {
  34. if (x < width - 1) // Checks if not on right edge
  35. if (maze[x + 1, y] != 1)
  36. if (!alreadyVisited(pathX, pathY, x + 1, y))
  37. {
  38. List < int > pX = new List < int > (pathX);
  39. List < int > pY = new List < int > (pathY);
  40. pX.Add(x + 1);
  41. pY.Add(y);
  42. pathXList.Add(pX);
  43. pathYList.Add(pY);
  44. }
  45. if (x > 0) // Checks if not on left edge
  46. if (maze[x - 1, y] != 1)
  47. if (!alreadyVisited(pathX, pathY, x - 1, y))
  48. {
  49. List < int > pX = new List < int > (pathX);
  50. List < int > pY = new List < int > (pathY);
  51. pX.Add(x - 1);
  52. pY.Add(y);
  53. pathXList.Add(pX);
  54. pathYList.Add(pY);
  55. }
  56. if (y > 0) // Checks if not on top edge
  57. if (maze[x, y - 1] != 1)
  58. if (!alreadyVisited(pathX, pathY, x, y - 1))
  59. {
  60. List < int > pX = new List < int > (pathX);
  61. List < int > pY = new List < int > (pathY);
  62. pX.Add(x);
  63. pY.Add(y - 1);
  64. pathXList.Add(pX);
  65. pathYList.Add(pY);
  66. }
  67. if (y < height - 1) // Checks if not on bottom edge
  68. if (maze[x, y + 1] != 1)
  69. if (!alreadyVisited(pathX, pathY, x, y + 1))
  70. {
  71. List < int > pX = new List < int > (pathX);
  72. List < int > pY = new List < int > (pathY);
  73. pX.Add(x);
  74. pY.Add(y + 1);
  75. pathXList.Add(pX);
  76. pathYList.Add(pY);
  77. }
  78. pathXList.RemoveAt(0);
  79. pathYList.RemoveAt(0);
  80. }
  81. pathNumber--;
  82. }
  83. }
  84. }
output

The program can be improved by adding a method of automatically generating mazes. There is already an article in C# Corner about it.