پرسش: یک جدول از حروف و یک کلمه کلیدی داریم. الگوریتمی بنویسید که مشخص کنید آیا کلمه کلیدی در جدول وجود دارد بگونه ای که حروف آن در جدول مجاور باشند. دو حرف مجاورند اگر بالا، راست، پایین، یا سمت چپ یکدیگر باشند. نمی توانیم از یک حرف در یک نقطه از جدول دوبار استفاده کنیم.
پاسخ: برای درک بهتر مساله حل آن را با یک مثال شروع می کنیم. اگر کلمه کلیدی Faces و جدول زیر را داشته باشیم، آنگاه الگوریتم باید مقدار True را برگرداند زیرا می توان کلمه Faces را از کنار هم گذاشتن حروف مجاور جدول (همانطور که با رنگ مشخص شده است) ساخت.
ابتدا الگوریتم جستجوی کامل را مطرح می کنیم. برای این پرسش الگوریتم جستجوی کامل شامل ایجاد همه کلمات ممکن متشکل از حروف مجاور را بسازیم. اگر کلمه کلیدی میان کلمات تولید شده باشد آنگاه مقدار True را برمی گردانیم. برای ساختن تمام کلمات متشکل از حروف مجاور در جدول باید از هر نقطه جدول شروع کنیم و به 4 جهت بالا، پایین، راست، و چپ حرکت کنیم. در حرکت به هر سمت به خانه جدیدی از جدول می رسیم. باید حرکت به بالا و پایین، راست و چپ بگونه ای انجام دهیم که به خانه قبلی برنگردیم. این کار را تا زمانی انجام می دهیم که به طول کلمه ایجاد شده معادل طول کلمه کلیدی باشد. پس از ایجاد یک کلمه آن را با کلمه کلیدی مقایسه می کنیم.
این روش را می توانیم با مقایسه تدریجی حروف کلمه ایجاد شده با کلمه کلیدی تسریع کنیم. با این صورت که خانه اول را با حرف اول کلمه کلیدی مقایسه می کنیم. چنانچه برابر نبودند عمل ایجاد کلمات از آن خانه را ادامه نمی دهیم. بنظر می رسد که راه حلی جز پیمایش کل ماتریس به این روش نداریم. اما چیزی که این بین کمک می کند راه حل را بهتر درک کنیم در نظر گرفتن مشابهت ارتباط بین خانه های جدول و یک گراف است. در واقع هر خانه جدول یک گره در گراف است و به گره هایی که در سمت راست، چپ، بالا، و پایین آن هستند متصل می شوند.
بنابر این الگوریتم تعریف شده در واقع یک جستجوی عمقی در گراف از هر گره آن می باشد. برای پیاده سازی نیاز به ساختن گره ها و اتصالات آنها به روش مرسوم ساخت گراف نمی باشد. شماره سطر ستون یک خانه از جدول برای یافتن گره هایی که در گراف همسایه هستند استفاده می شوند.
بنابر این شروع به پیاده سازی برنامه می کنیم. ابتدا نام تابع و پارامترهای مناسب را تعریف می کنیم (خط 1). سپس تعداد سطر و ستون جدول را در متغیر هایی می گذاریم که بعدا بتوانیم راحت از آنها استفاده کنیم (خط 2 و 3). به دلیل مشابه طول کلمه کلیدی را در متغیری می گذاریم (خط 4). سپس یک ماتریس به عنوان سایه ماتریس اصلی با مقادیر اولیه False برای همه خانه های می سازیم (خط 5 و 6). در ادامه پیاده سازی با تغییر مقدار خانه های این جدول به True از استفاده مجدد یک حرف در ایجاد یک کلمه جلوگیری می کنیم. برای فرمول کردن حرکت به راست، چپ، بالا، و پایین از یک لیست از لیست ها استفاده می کنیم (خط 7). هر عنصر لیست دارای دو عنصر است که اولین عنصر میزان حرکت در سطر و دومی در ستون را برای رسیدن به عنصر مجاور مناسب نشان می دهد. تابع داخلی dfs در واقع از خانه (i , j)جدول شروع به یافتن ادامه کلمه کلیدی (از اندیس seq به بعد) می کند (خط 9). قبل از تشریح داخل این تابع سراغ مابقی سطرهای برنامه می کنیم. خط 25 تا 28 در دو حلقه تکرار تو در تو ماتریس را می پیماید و امتحان می کند که آیا می توان کلمه کلیدی را از یک خانه ماتریس ساخت. برای تشخیص این امر هر بار تابع داخلی را فراخوانی می کند (خط 27). حال به تشریح تابع داخلی ادامه می دهیم. این یک تابع بازگشتی است و خود را فراخوانی می کند تا جایی که با انتهای کلمه کلیدی نرسیده ایم و همچنان حروف جدول در مسیر پیموده شده با حروف کلمه کلیدی برابرند. به این دلیل هر بار حرف در موقعیت (i, j)ماتریس را با عنصر موقعیت seq در کلمه کلیدی مقایسه می کنیم. در صورتی که برابر نباشند این مسیر را ادامه نمی دهیم (خط 22 و 23). در صورتی که برابر باشند و این آخرین حرف در کلمه کلیدی باشد با این معناست که کلمه کلیدی در جدول موجود است (خط 11 و 12). اگر به انتهای کلمه کلیدی نرسیده باشیم باید این خانه (i, j) را نشان گذاری کنیم تا در ادامه مسیر کنونی از آن دوباره استفاده نکنیم (خط 13). سپس برای هر یک از جهت های حرکت در یک حلقه تکرار (خط 14) اندیس موقعیت های بعدی را می سازیم (خط 15 و 16). آنگاه بررسی می کنیم که اندیس ها خارج از ماتریس نیفتاده باشند و همچنین خانه مورد نظر قبلا در این مسیر استفاده نشده باشد (خط 17 و 18). در صورت امکان حرکت به نقطه جدید تابع را بصورت بازگشتی فراخوانی می کنیم (خط 19). در صورتی که حاصل جستجو موفقیت آمیز باشد به جستجو خاتمه می دهیم (خط 20). در صورتی که جستجو موفقیت آمیز نبود نشان خانه (i, j) را به false تنظیم می کنیم تا مسیر بعدی بتواند برای تشکیل کلمات از آن استفاده نماید (خط 22).
