I am trying to solve a maze using backtracking in C. To solve the maze the following rules:
The input consists of a m x n matrix: Input example:
11 11
+-+-+-+-+-+
S.|...|...|
+.+.+.+-+.+
|.|.|.....|
+.+-+-+-+.+
|...|.|...|
+.+.+.+.+-+
|.|...|.|.|
+.+-+.+.+.+
|...|.....E
+-+-+-+-+-+
Expected solution :
+-+-+-+-+-+
##|...|...|
+#+.+.+-+.+
|#|.|.....|
+#+-+-+-+.+
|###|.|...|
+.+#+.+.+-+
|.|###|.|.|
+.+-+#+.+.+
|...|######
+-+-+-+-+-+
I am trying really hard to solve it but for some reason my program doesn't go back once I reached a point in the maze from where I can't go further.It just go in all the directions where it sees a '.'
My idea was to start from the position of S and using at each recursion step the old position that we were. I will go in all the direction from the position where I am standing if the position that I am looking at is a '.' and if that point was not my old position.
I also think that I have a problem when i reach a point where it was a crossroad when I backtrack. For example:
+-+-+-+-+-+
##|...|...|
+#+.+.+-+.+
|#|.|.....|
+#+-+-+-+.+
|0##|.|...|
+.+#+.+.+-+
|.|###|.|.|
+.+-+#+.+.+
|..1|######
+-+-+-+-+-+
Imagine that I am in the position 0. And I backtracked from 1 changing back the # into '.'.How can I make a statement saying that you have 2 # possibilities to go back , yet you should stop?
My code :
#include <stdio.h>
#include <stdlib.h>
void *safeMalloc(int n) {
void *p = malloc(n);
if (p == NULL) {
printf("Error: malloc(%d) failed. Out of memory?\n", n);
exit(EXIT_FAILURE);
}
return p;
}
char ** readMatrix(int m,int n,int* startI,int* startJ,int* endI,int* endJ){
char **arr = safeMalloc(m*sizeof(char *));
int row;
for (row=0; row < m; row++) {
arr[row] = safeMalloc(n*sizeof(char));
}
int i,j;
for(i=0;i<m;i++){
for(j=0;j<m;j++){
scanf(" %c",&arr[i][j]);
if(arr[i][j]=='S'){
*startI=i;
*startJ=j;
}
if(arr[i][j]=='E'){
*endI=i;
*endJ=j;
}
}
getchar();
}
return arr;
}
void printNumber(char **arr,int m,int n){
int i,j;
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf("%c", arr[i][j]);
}
printf("\n");
}
}
void findPath(char** arr,int m,int n,int startI,int startJ,int endI,int endJ,int oldI,int oldJ){
int i=startI,j=startJ;
int stepsPossible=4;
//going up
if(i-1>=0){
if((arr[i-1][j]=='.') && ((i-1!=oldI) || (j!=oldJ))){
arr[i][j]='#';
oldI=i;
oldJ=j;
findPath(arr,m,n,i-1,j,endI,endJ,oldI,oldJ);
}else{
stepsPossible--;
}
}
//going right
if(j+1<n){
if((arr[i][j+1]=='.') && ((i!= oldI) || (j+1!=oldJ))){
arr[i][j]='#';
oldI=i;
oldJ=j;
findPath(arr,m,n,i,j+1,endI,endJ,oldI,oldJ);
}else{
stepsPossible--;
}
}
//going left
if(j-1>=0){
if((arr[i][j-1]=='.') && ((i!= oldI) || (j-1!=oldJ))){
arr[i][j]='#';
oldI=i;
oldJ=j;
findPath(arr,m,n,i,j-1,endI,endJ,oldI,oldJ);
}else{
stepsPossible--;
}
}
//going down
if(i+1<m){
if((arr[i+1][j]=='.') && ((i+1!= oldI) || (j!=oldJ))){
arr[i][j]='#';
oldI=i;
oldJ=j;
findPath(arr,m,n,i+1,j,endI,endJ,oldI,oldJ);
}else{
stepsPossible--;
}
}
//if the next block is E then we can stop.
if((arr[i-1][j]=='E') || (arr[i][j+1]=='E') || (arr[i][j-1]=='E') || (arr[i+1][j]=='E')){
if(arr[i-1][j]=='E'){
arr[i-1][j]='#';
}
if(arr[i][j+1]=='E'){
arr[i][j+1]='#';
}
if(arr[i][j-1]=='E'){
arr[i][j-1]='#';
}
if(arr[i+1][j]=='E'){
arr[i+1][j]='#';
}
return;
}
if(stepsPossible==0){
if(arr[i-1][j]=='#'){
arr[i][j]='.';
oldI=i;
oldJ=j;
findPath(arr,m,n,i-1,j,endI,endJ,oldI,oldJ);
}else{
return;
}
if(arr[i][j+1]=='#' ){
arr[i][j]='.';
oldI=i;
oldJ=j;
findPath(arr,m,n,i,j+1,endI,endJ,oldI,oldJ);
}else{
return;
}
if(arr[i][j-1]=='#' ){
arr[i][j]='.';
oldI=i;
oldJ=j;
findPath(arr,m,n,i,j-1,endI,endJ,oldI,oldJ);
}else{
return;
}
if(arr[i+1][j]=='#' ){
arr[i][j]='.';
oldI=i;
oldJ=j;
findPath(arr,m,n,i+1,j,endI,endJ,oldI,oldJ);
}else{
return;
}
}
}
int main()
{
int m,n;
scanf("%d %d",&m,&n);
int startI,startJ,endI,endJ;
char** arr;
arr=readMatrix(m,n,&startI,&startJ,&endI,&endJ);
findPath(arr,m,n,startI,startJ,endI,endJ,startI,startJ);
printNumber(arr,m,n);
return 0;
}
Make proper use of the return value, as you can utilize it to simplify your logic. Choose different return values on findPath for the error case (backtracking necessary) and the success case (end reached).
Now you can put setting the # unconditionally in the start of that function, and resetting back to . unconditionally in the end for the backtracking case.
There is no need to count possible directions either, only checking if some call returned success.
Also no need to write the boundary checks over and over again, if you just check them at the start of the function you can just pass invalid coordinates without any issues.
bool findPath(char** arr, size_t sx, size_t sy, int x, int y) {
if (x < 0 || x >= sx || y < 0 || y >= sy) return false;
if (arr[x][y] == 'E') {
are[x][y] = '#';
return true;
}
if (arr[x][y] != '.') return false;
arr[x][y] = '#';
bool success = findPath(arr, sx, sy, x-1, y) ||
findPath(arr, sx, sy, x+1, y) ||
findPath(arr, sx, sy, x, y-1) ||
findPath(arr, sx, sy, x, y+1);
if (!success) arr[x][y] = '.';
return success;
}
Implementations for backtracking algorithms usually all follow the same pattern: