Solving Maze c#

Question

I want to solve a maze automatically when I run the program.

My maze is like this at the beginning.

1 0 0 0
0 0 1 0
0 1 1 0
0 1 1 0

At the end it should look like this :

0 1 1 1
1 1 0 1
1 0 0 1
1 0 0 1

I have an array of 3 dimensions ( for row, columns and side).

Sides can be under(0),right(1),above(2) and left(3). So I check for each cell if I have a wall. If yes, I put yes in that cell.

mazeTab[0, 0, 0] = 0;
mazeTab[0, 0, 1] = 1;
mazeTab[0, 0, 2] = 1;
mazeTab[0, 0, 3] = 1;

mazeTab[1, 0, 0] = 0;
mazeTab[1, 0, 1] = 0;
mazeTab[1, 0, 2] = 1;
mazeTab[1, 0, 3] = 1;

mazeTab[2, 0, 0] = 0;
mazeTab[2, 0, 1] = 0;
mazeTab[2, 0, 2] = 1;
mazeTab[2, 0, 3] = 0;

mazeTab[3, 0, 0] = 0;
mazeTab[3, 0, 1] = 1;
mazeTab[3, 0, 2] = 1;
mazeTab[3, 0, 3] = 0;
//=================================

mazeTab[0, 1, 0] = 0;
mazeTab[0, 1, 1] = 0;
mazeTab[0, 1, 2] = 1;
mazeTab[0, 1, 3] = 1;

mazeTab[1, 1, 0] = 1;
mazeTab[1, 1, 1] = 1;
mazeTab[1, 1, 2] = 0;
mazeTab[1, 1, 3] = 0;

mazeTab[2, 1, 0] = 1;
mazeTab[2, 1, 1] = 1;
mazeTab[2, 1, 2] = 1;
mazeTab[2, 1, 3] = 1;

mazeTab[3, 1, 0] = 0;
mazeTab[3, 1, 1] = 1;
mazeTab[3, 1, 2] = 0;
mazeTab[3, 1, 3] = 1;
//===================================
mazeTab[0, 2, 0] = 0;
mazeTab[0, 2, 1] = 1;
mazeTab[0, 2, 2] = 0;
mazeTab[0, 2, 3] = 1;

mazeTab[1, 2, 0] = 1;
mazeTab[1, 2, 1] = 1;
mazeTab[1, 2, 2] = 1;
mazeTab[1, 2, 3] = 1;

mazeTab[2, 2, 0] = 1;
mazeTab[2, 2, 1] = 1;
mazeTab[2, 2, 2] = 1;
mazeTab[2, 2, 3] = 1;

mazeTab[3, 2, 0] = 0;
mazeTab[3, 2, 1] = 1;
mazeTab[3, 2, 2] = 0;
mazeTab[3, 2, 3] = 1;
//===================================
mazeTab[0, 3, 0] = 1;
mazeTab[0, 3, 1] = 1;
mazeTab[0, 3, 2] = 0;
mazeTab[0, 3, 3] = 1;

mazeTab[1, 3, 0] = 1;
mazeTab[1, 3, 1] = 1;
mazeTab[1, 3, 2] = 1;
mazeTab[1, 3, 3] = 1;

mazeTab[2, 3, 0] = 1;
mazeTab[2, 3, 1] = 1;
mazeTab[2, 3, 2] = 1;
mazeTab[2, 3, 3] = 1;

mazeTab[3, 3, 0] = 0;
mazeTab[3, 3, 1] = 1;
mazeTab[3, 3, 2] = 0;
mazeTab[3, 3, 3] = 1;

Then I use a method to solve the whole maze, but I'm pretty sure something is wrong. When I use it, I check if the next cell, example: if I have a 0 and I can go above, I check if the cell above can also go to the cell under, to verify that we don't have a wall in there.

   int solvemaze(int horizontal, int vertical,int cote)
    {

        //horizontalestination is the last cell(maze[taille-1][taille-1])
        if ((horizontal == taille - 1) && (vertical == taille - 1))
        {
            solution[horizontal,vertical] = 1;
            return 1;
        }

        if (horizontal >= 0 && vertical >= 0 && horizontal < taille && vertical < taille && solution[horizontal,vertical] == 0)
        {

            printsolution();
            //if safe to visit then visit the cell
            solution[horizontal,vertical] = 1;
            //under
            if (mazeTab[horizontal,vertical,cote]==0)
                return solvemaze(horizontal,vertical+1,(cote+1)%4);
            cote = (cote + 1) % 4;
            //right
            if (mazeTab[horizontal, vertical, 1] == 0)
                return solvemaze(horizontal+1, vertical, (cote + 1)% 4);
            cote = (cote + 1) % 4;
            //up
            if (mazeTab[horizontal, vertical, 2] == 0)
                return solvemaze(horizontal, vertical -1, (cote + 1) % 4);
            cote = (cote + 1) % 4;
            //left
            if (mazeTab[horizontal, vertical, 3] == 0)
                return solvemaze(horizontal -1, vertical, (cote + 1) % 4);
            cote = (cote + 1) % 4;
            //backtracking
            solution[horizontal,vertical] = 0;
            return 1;
        }
        return 1;

Just to remind you that if u can go to a specific cell, then it's 1. So the path to solve the maze is full of 1.

And last, I start the maze at the cell 0,3,0, which is this one:

1 0 0 0
0 0 1 0
0 1 1 0
**0** 1 1 0

When I run, here's what I get instead:

0 1 1 1 
1 1 0 0 
1 0 0 0 
0 0 0 0

The following 0 should have turned in 1..

0 1 1 1 
1 1 0 **0** 
1 0 0 **0** 
**0** 0 0 **0**

Can you guys help me find the error?

Pleo

1. could you update the question to include more maze inputs and expected outputs? 2. A good starting point would be to decompose the array into a two dimension array. The side dimension could be replaced with a bitflag enum for example. – Reconstructionist

Hello, I've updated my question, and for the array, I have to do in a 3 dimension, school rules for the project.. – Pleo

In the if blocks, you should check the return value of solvemaze(...) and only return the result if it is 1. After the backtracking, you should return 0 instead of 1. – Pneumogastric

Answer 1

Thanks to @HHLV, I've figured it out how to solve this problem.

So my method solvemaze looks like this :

int solvemaze(int horizontal, int vertical, int cote)
    {


        if ((horizontal == taille - 1) && (vertical == taille - 1))
        {
            solution[vertical, horizontal] = 1;
            return 1;
        }

        if (horizontal >= 0 && vertical >= 0 && horizontal < taille && vertical < taille && solution[vertical, horizontal] == 0)
        {

            printsolution();
            //if safe to visit then visit the cell
            solution[vertical, horizontal] = 1;

            for (int i = 0; i < 3; i++)
            {

                if (mazeTab[horizontal, vertical, cote] == 0)
                {
                    if (cote == 0 && solvemaze(horizontal, vertical + 1, (cote + 3) % 4) == 1)
                    {
                        return 1;
                    }
                    else if (cote == 1 && solvemaze(horizontal + 1, vertical, (cote + 3) % 4) == 1)
                    {
                        return 1;

                    }
                    else if (cote == 2 && solvemaze(horizontal, vertical - 1, (cote + 3) % 4) == 1)
                    {
                        return 1;

                    }
                    else if (cote == 3 && solvemaze(horizontal - 1, vertical, (cote + 3) % 4) == 1)
                    {
                        return 1;

                    }
                }
                cote = (cote + 1) % 4;

            }

            //backtracking
            solution[vertical, horizontal] = 0;

            return 0;
        }
        return 0;

    }

And know it works, thank you !

Pleo