भूलभुलैया में चूहा भी एक लोकप्रिय समस्या है जो बैकट्रैकिंग का उपयोग करती है। मैं
भूलभुलैया एक 2डी मैट्रिक्स है जिसमें कुछ कोशिकाएं अवरुद्ध होती हैं। कोशिकाओं में से एक स्रोत सेल है, जहां से हमें शुरू करना है। और उनमें से एक दूसरी मंजिल है, जहां हमें पहुंचना है। हमें किसी भी अवरुद्ध सेल में जाए बिना स्रोत से गंतव्य तक का रास्ता खोजना होगा। एक अनसुलझी भूलभुलैया का चित्र नीचे दिखाया गया है।
और यही इसका समाधान है।
इस पहेली को हल करने के लिए, हम पहले स्रोत सेल से शुरू करते हैं और उस दिशा में आगे बढ़ते हैं जहां पथ अवरुद्ध नहीं है। अगर रास्ता लिया जाए तो हम मंजिल तक पहुंच जाते हैं तो पहेली सुलझ जाती है। नहीं तो हम वापस आ जाते हैं और अपने द्वारा लिए गए रास्ते की दिशा बदल देते हैं। हम उसी तर्क को अपने कोड में भी लागू करने जा रहे हैं।
Input:
maze[][] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}}
Output:
1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1 स्पष्टीकरण
सबसे पहले, हम भूलभुलैया का प्रतिनिधित्व करने के लिए एक मैट्रिक्स बनाएंगे, और मैट्रिक्स के तत्व या तो 0 या 1 होंगे। 1 अवरुद्ध सेल का प्रतिनिधित्व करेगा और 0 उन कोशिकाओं का प्रतिनिधित्व करेगा जिनमें हम स्थानांतरित हो सकते हैं। ऊपर दिखाए गए भूलभुलैया के लिए मैट्रिक्स है:
0 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0
अब, हम समाधान को संग्रहीत करने के लिए उसी आयाम का एक और मैट्रिक्स बनाएंगे। इसके तत्व भी 0 या 1 होंगे। 1 हमारे पथ में कोशिकाओं का प्रतिनिधित्व करेगा और शेष कोशिकाएं 0 होंगी। समाधान का प्रतिनिधित्व करने वाला मैट्रिक्स है:
1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1
इस प्रकार, अब हमारे पास हमारे मैट्रिक्स हैं। इसके बाद, हमें स्रोत सेल से गंतव्य सेल तक का रास्ता मिलेगा और हम जो कदम उठाएंगे वे हैं:
-
वर्तमान सेल की जाँच करें, यदि यह गंतव्य सेल है, तो पहेली हल हो जाती है।
-
यदि नहीं, तो हम नीचे की ओर बढ़ने की कोशिश करेंगे और देखेंगे कि हम नीचे की ओर जाने वाले सेल में जा सकते हैं या नहीं (सेल में जाने के लिए यह खाली होना चाहिए और पहले से ही पथ में मौजूद नहीं होना चाहिए)।
-
अगर हम वहां जा सकते हैं, तो हम अगले डाउनवर्ड सेल में ले जाने वाले रास्ते पर चलते रहेंगे।
-
यदि नहीं, तो हम दाएँ कक्ष में जाने का प्रयास करेंगे। और अगर इसे ब्लॉक या लिया गया है, तो हम ऊपर की ओर बढ़ेंगे।
-
इसी तरह, अगर हम ऊपर भी नहीं जा सकते हैं, तो हम बस बाएं सेल में चले जाएंगे।
-
यदि चार चालों (नीचे, दाएं, ऊपर, या बाएं) में से कोई भी संभव नहीं है, तो हम बस वापस चले जाएंगे और अपना वर्तमान पथ (बैकट्रैकिंग) बदल देंगे।
इस प्रकार, सारांश यह है कि हम वर्तमान सेल से दूसरे सेल (नीचे, दाएं, ऊपर और बाएं) में जाने की कोशिश करते हैं और यदि कोई गति संभव नहीं है, तो बस वापस आएं और पथ की दिशा को दूसरे सेल में बदलें।
Printsolution → यह फ़ंक्शन केवल सॉल्यूशन मैट्रिक्स को प्रिंट कर रहा है।
सॉल्वमेज़ → यह वास्तविक कार्य है जहाँ हम बैकट्रैकिंग एल्गोरिथम को लागू कर रहे हैं। सबसे पहले, हम अपने सेल की जाँच कर रहे हैं कि गंतव्य सेल है या नहीं (r==SIZE-1) और (c==SIZE-1)। यदि यह गंतव्य सेल है तो हमारी पहेली पहले ही हल हो चुकी है। यदि नहीं, तो हम जांच कर रहे हैं कि यह स्थानांतरित करने के लिए एक वैध सेल है या नहीं। एक वैध सेल मैट्रिक्स में होना चाहिए यानी, इंडेक्स 0 से SIZE-1 r>=0 &&c>=0 &&rउदाहरण
#include <iostream>
using namespace std;
#define SIZE 5
//the maze problem
int maze[SIZE][SIZE] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}
};
//matrix to store the solution
int solution[SIZE][SIZE];
//function to print the solution matrix
void printsolution() {
int i,j;
for(i=0;i<SIZE;i++) {
for(j=0;j<SIZE;j++) {
printf("%d\t",solution[i][j]);
}
printf("\n\n");
}
}
//function to solve the maze
//using backtracking
int solvemaze(int r, int c) {
//if destination is reached, maze is solved
//destination is the last cell(maze[SIZE-1][SIZE-1])
if((r==SIZE-1) && (c==SIZE-1) {
solution[r][c] = 1;
return 1;
}
//checking if we can visit in this cell or not
//the indices of the cell must be in (0,SIZE-1)
//and solution[r][c] == 0 is making sure that the cell is not already visited
//maze[r][c] == 0 is making sure that the cell is not blocked
if(r>=0 && c>=0 && r<SIZE && c<SIZE && solution[r][c] == 0 && maze[r][c] == 0){
//if safe to visit then visit the cell
solution[r][c] = 1;
//going down
if(solvemaze(r+1, c))
return 1;
//going right
if(solvemaze(r, c+1))
return 1;
//going up
if(solvemaze(r-1, c))
return 1;
//going left
if(solvemaze(r, c-1))
return 1;
//backtracking
solution[r][c] = 0;
return 0;
}
return 0;
}
int main() {
//making all elements of the solution matrix 0
int i,j;
for(i=0; i<SIZE; i++) {
for(j=0; j<SIZE; j++) {
solution[i][j] = 0;
}
}
if (solvemaze(0,0))
printsolution();
else
printf("No solution\n");
return 0;
}