પુનરાવર્તિત બેકટ્રેકર મેઝ જનરેટર

પુનરાવર્તિત બેકટ્રેકર એલ્ગોરિધમ ખરેખર સામાન્ય હેતુની ઊંડાઈ-પ્રથમ શોધ છે. જ્યારે ભુલભુલામણીના સર્જન માટે તેનો ઉપયોગ કરવામાં આવે છે, ત્યારે તે રેન્ડમ પર પાથ પસંદ કરવા માટે થોડો ફેરફાર કરે છે, જ્યારે જો તેનો ઉપયોગ વાસ્તવિક શોધ હેતુઓ માટે કરવામાં આવે તો, વ્યક્તિ સામાન્ય રીતે રેખીય ક્રમમાં દરેક સ્તરને શોધી શકે છે. તે લાંબા, વળાંકવાળા કોરિડોર અને ખૂબ જ લાંબા, ટ્વિસ્ટિંગ સોલ્યુશન સાથે મેઝનું ઉત્પાદન કરવાનું વલણ ધરાવે છે.

સંપૂર્ણ ભુલભુલામણી એ એક ભુલભુલામણી છે જેમાં ભુલભુલામણીના કોઈપણ બિંદુથી બીજા કોઈપણ બિંદુ સુધીનો એક જ રસ્તો હોય છે. તેનો અર્થ એ કે તમે વર્તુળોમાં ફરતા રહી શકતા નથી, પરંતુ તમને ઘણીવાર મૃત છેડાઓનો સામનો કરવો પડશે, જેના કારણે તમને પાછળ ફરીને પાછા ફરવું પડશે.

અહીં જનરેટ થયેલા મેઝ મેપ્સમાં કોઈ પણ શરૂઆત અને સમાપ્તિ સ્થિતિ વિના ડિફોલ્ટ સંસ્કરણ શામેલ છે, તેથી તમે તે જાતે નક્કી કરી શકો છો: મેઝના કોઈપણ બિંદુથી બીજા કોઈપણ બિંદુ સુધી ઉકેલ હશે. જો તમને પ્રેરણા જોઈતી હોય, તો તમે સૂચવેલ શરૂઆત અને સમાપ્તિ સ્થિતિને સક્ષમ કરી શકો છો - અને બંને વચ્ચેનો ઉકેલ પણ જોઈ શકો છો.

પુનરાવર્તિત બેકટ્રેકર એલ્ગોરિધમ એ સંપૂર્ણ મેઝ (કોઈ લૂપ્સ વિનાના મેઝિસ અને કોઈપણ બે બિંદુઓ વચ્ચે એક જ પાથ) ઉત્પન્ન કરવા માટે ડેપ્થ-ફર્સ્ટ શોધ પદ્ધતિ છે. તે સરળ, કાર્યક્ષમ છે અને લાંબા, ઘુમાવદાર કોરિડોર સાથે દૃષ્ટિની આકર્ષક મેઝનું ઉત્પાદન કરે છે.

તેનું નામ હોવા છતાં, તે પુનરાવર્તનનો ઉપયોગ કરીને અમલમાં મૂકવામાં આવે તે જરૂરી નથી. તે ઘણીવાર LIFO કતાર (એટલે કે સ્ટેક)નો ઉપયોગ કરીને પુનરાવર્તિત અભિગમમાં અમલમાં મૂકવામાં આવે છે. ખૂબ મોટી ભુલભુલામણી માટે, પુનરાવર્તનનો ઉપયોગ કરવાથી પ્રોગ્રામિંગ લેંગ્વેજ અને ઉપલબ્ધ મેમરીના આધારે કોલ સ્ટેક ઓવરફ્લો થવાની શક્યતા વધારે છે. LIFO કતારને વધુ સરળતાથી મોટી માત્રામાં ડેટાનું સંચાલન કરવા માટે સ્વીકારી શકાય છે, જો ઉપલબ્ધ મેમરી અપૂરતી હોય તો કતારને ડિસ્ક પર અથવા ડેટાબેઝમાં પણ રાખી શકાય છે.

તે કેવી રીતે કાર્ય કરે છે

એલ્ગોરિધમ સ્ટેક-આધારિત ડેપ્થ-ફર્સ્ટ સર્ચ અભિગમનો ઉપયોગ કરીને કામ કરે છે. અહીં સ્ટેપ-બાય-સ્ટેપ બ્રેકડાઉન આપવામાં આવ્યું છે:

1. પ્રારંભિક સેલ પસંદ કરો અને મુલાકાત લીધા મુજબ તેને ચિહ્નિત કરો.
2. જ્યારે ત્યાં વણશોધાયેલા કોષો હોય છે:
   • પડોશી કોષો તરફ જુઓ કે જેની હજી સુધી મુલાકાત લેવામાં આવી નથી.
   • જો ઓછામાં ઓછો એક મુલાકાત ન લેવાયેલ પડોશી અસ્તિત્વમાં હોય તો:
     • મુલાકાત ન લેવાયેલા પડોશીઓમાંથી કોઈ એકને અવ્યવસ્થિત રીતે પસંદ કરો.
     • વર્તમાન સેલ અને પસંદ કરેલા પાડોશી વચ્ચેની દિવાલને દૂર કરો.
     • પસંદ કરેલા પાડોશી પાસે જાઓ અને મુલાકાત લીધા પ્રમાણે તેને ચિહ્નિત કરો.
     • વર્તમાન સેલને સ્ટેક પર દબાવો.
   • જો કોઈ મુલાકાત ન થયેલ પાડોશીઓ અસ્તિત્વમાં ન હોય તો:
     • સ્ટેકમાંથી છેલ્લા સેલને પોપ કરીને બેકટ્રેક.
3. જ્યાં સુધી સ્ટેક ખાલી ન થાય ત્યાં સુધી આ પ્રક્રિયા ચાલુ રાખો.

આ અલ્ગોરિધમનો વિશેની એક રસપ્રદ તથ્ય એ છે કે તે ભુલભુલામણી જનરેટર અને ભુલભુલામણી ઉકેલનાર તરીકે બંને કાર્ય કરે છે. જો તમે તેને પહેલેથી જ પેદા થયેલી ભુલભુલામણી પર ચલાવો છો અને જ્યારે તમે નક્કી કરેલા અંતિમ બિંદુને સ્પર્શો ત્યારે જ અટકી જાઓ છો, તો સ્ટેક ભુલભુલામણીના ઉકેલને સમાવી લેશે.

આ સાઇટ પર મારી પાસે ખરેખર આ એલ્ગોરિધમની બે આવૃત્તિઓ છે: એક LIFO કતાર આ પૃષ્ઠ પર મેઝ ઉત્પન્ન કરવા માટે આધારિત છે અને મેઝને હલ કરવા માટે પુનરાવર્તિત એક છે, તે પણ અન્ય એલ્ગોરિધમ્સ દ્વારા જનરેટ કરવામાં આવેલી મેઝિસ (તે જ રીતે ઉકેલો સાથેના નકશાબનાવવામાં આવે છે). બે અલગ અલગ સંસ્કરણો રાખવા એ માત્ર રમતગમત માટે છે કારણ કે હું એક મૂર્ખ છું જેને તે રસપ્રદ લાગે છે, કાં તો તે બંને માટે કામ કરી શક્યું હોત ;-)