In this homework assignment, I need to implement a maze solver using divide and

Question

In this homework assignment, I need to implement a maze solver using divide and
conquer.
The Maze Problem: The input is an n x n maze and a start position and an exit position. Your
program needs to decide whether there is path from the start to the exit. If yes, then print the path
in a sequence of position coordinates from the start to the exit.
How to Represent a Maze: You can use a 2D array of characters. The input is from a text file.
For example, the following is a 6x6 maze:
X X S X X X
X O O O O X
X X X O O X
X O X O X X
X O O O O X
X X X X E X
Here, “X” stands for a block, “O” for an open area, “S” for the start, and “E” for the exit.
How to Output a Path: Just output the coordinates of the positions. For example for the above
ex example, the path is
S=(0, 3), (1, 2), (1, 3), (2, 3), (3, 3), (4, 3), (4, 4), E=(5, 4)

Explanation / Answer

i hope everyone know what is maze problem. so i going directly to the program

step 1:: for convienence i converted x into 1 and o as 0 then the above maze becomes where s always starts from 1 and e starts from 0.

maze[N][N] = { {1, 1, 0, 1, 1, 1},
        {1, 0, 0, 0, 0, 1},
        {1, 1, 1, 0, 0, 1},
        {1, 0, 1, 0, 1, 1},
        {1, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1}
    };

so the program will become.

#include<stdio.h>

#define N 6

bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);

void printSolution(int sol[N][N])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            printf(" %d ", sol[i][j]);
        printf(" ");
    }
}

bool isSafe(int maze[N][N], int x, int y)
{
    if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
        return true;

    return false;
}

bool solveMaze(int maze[N][N])
{
    int sol[N][N] = { {0, 0, 0, 0,0,0},
        {0, 0, 0, 0, 0 ,0},
        {0, 0, 0, 0 ,0 ,0},
        {0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0}
    };

    if(solveMazeUtil(maze, 0, 0, sol) == false)
    {
        printf("Solution doesn't exist");
        return false;
    }

    printSolution(sol);
    return true;
}

bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
    if(x == N-1 && y == N-1)
    {
        sol[x][y] = 1;
        return true;
    }

    if(isSafe(maze, x, y) == true)
    {
        sol[x][y] = 1;

        if (solveMazeUtil(maze, x+1, y, sol) == true)
            return true;

        if (solveMazeUtil(maze, x, y+1, sol) == true)
            return true;

        sol[x][y] = 0;
        return false;
    }

    return false;
}

int main()
{
    int maze[N][N] = { {1, 1, 0, 1, 1, 1},
        {1, 0, 0, 0, 0, 1},
        {1, 1, 1, 0, 0, 1},
        {1, 0, 1, 0, 1, 1},
        {1, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1}
    };

    solveMaze(maze);
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.