معمای گرگ و گوسفند و کلم

**معمای گرگ و گوسفند و کلم** (Wolf, Sheep and Cabbage) یک مسئله کلاسیک در هوش مصنوعی است. این مسئله نمونه‌ای از مسائل ارضای محدودیت می‌باشد.
یک کشاورز می‌خواهد یک گرگ، یک گوسفند و یک بسته کلم را از یک طرف رودخانه به طرف دیگر رودخانه ببرد، ولی قایق او فقط برای خودش و یکی از آنها جا دارد. اگر گرگ و گوسفند تنها باشند، گرگ گوسفند را خواهد خورد و اگر گوسفند و کلم تنها باشند، گوسفند کلم را خواهد خورد.
این مسئله به صورت معمای روباه و غاز و کیسه عدس (Fox, goose and bag of beans puzzle) نیز تعریف شده است.
این سه مسئله یعنی معمای زن و شوهرهای حسود، معمای کشیش‌ها و آدمخوارها و 'معمای گرگ و گوسفند و کلم' به مسائل ردشدن از رودخانه معروف هستند.

## تاریخچه و نسخه‌های مختلف معما
معمای گرگ و گوسفند و کلم، ریشه‌ای کهن دارد و در فرهنگ‌های مختلف با اشکال گوناگونی روایت شده است. این معما اولین بار در قرون وسطی در اروپا ثبت شده و نسخه‌هایی از آن در نوشته‌های راهبان و متفکران دیده می‌شود. ازجمله مشهورترین نسخه‌های مشابه آن می‌توان به موارد زیر اشاره کرد:

### '''معمای روباه، غاز و کیسه عدس''' (Fox, Goose and Bag of Beans Puzzle)
در این نسخه، یک مرد باید روباه، غاز و یک کیسه عدس را از رودخانه عبور دهد.

### '''معمای کشیش‌ها و آدمخوارها''' (Missionaries and Cannibals)
در این معما، چند کشیش و آدمخوار باید با یک قایق از رودخانه عبور کنند، اما اگر تعداد آدمخوارها در هر طرف بیشتر از کشیش‌ها باشد، کشیش‌ها خورده می‌شوند.

### '''معمای زن و شوهرهای حسود'''
در این مسئله، چند زوج باید از رودخانه عبور کنند، اما هیچ زنی نباید بدون حضور شوهرش کنار مردان دیگر بماند.

همه این مسائل به **مسائل ردشدن از رودخانه (River Crossing Problems)** معروف هستند که در آن‌ها قوانین محدودکننده باعث پیچیدگی حل مسئله می‌شوند.

## راه حل
# برای حل این معما، کشاورز باید برنامه‌ریزی کند که چگونه گرگ، گوسفند و کلم را طوری جابه‌جا کند که قوانین رعایت شوند. راه‌حل استاندارد این مسئله به صورت زیر است:

# کشاورز ابتدا **گوسفند** را به طرف دیگر رودخانه می‌برد و او را در آنجا می‌گذارد.
# سپس برمی‌گردد و **گرگ** را با خود به طرف دیگر می‌برد.
# در این مرحله، کشاورز **گوسفند را برمی‌گرداند** و در سمت اول رودخانه می‌گذارد.
# سپس **کلم را به سمت دیگر می‌برد** و کنار گرگ قرار می‌دهد.
# در نهایت، کشاورز برمی‌گردد و **گوسفند را به طرف دیگر رودخانه منتقل می‌کند**.

**نتیجه:** همه‌ی آیتم‌ها بدون تخطی از قوانین به طرف دیگر رودخانه منتقل می‌شوند.

## تحلیل ریاضی و الگوریتمی
برای درک بهتر این معما از دیدگاه محاسباتی، می‌توان آن را به‌صورت یک مدل ریاضی و گرافی نمایش داد که در آن، هر وضعیت یک **گره (Node)** و هر حرکت قانونی یک **یال (Edge)** در گراف محسوب می‌شود.

### مدل‌سازی به‌عنوان یک مسئله گرافی
این مسئله را می‌توان به‌صورت یک **گراف جهت‌دار** مدل‌سازی کرد که در آن، هر **گره** (Node) نشان‌دهنده‌ی یک حالت ممکن از موقعیت کشاورز، گرگ، گوسفند و کلم است و هر **یال** (Edge) نشان‌دهنده‌ی حرکتی قانونی است که کشاورز انجام می‌دهد.

در این مدل:

* **هر حالت** شامل موقعیت چهار متغیر (کشاورز، گرگ، گوسفند، کلم) است.
* **انتقال از یک حالت به حالت دیگر**، یعنی عبور از رودخانه با یک آیتم، تحت شرایط خاص امکان‌پذیر است.
* **هدف**، یافتن یک مسیر از حالت شروع به حالت پایانی است.

### الگوریتم حل با BFS (جستجوی اول سطح)
یکی از روش‌های رایج برای یافتن راه‌حل بهینه در این معما، استفاده از الگوریتم **BFS (جستجوی سطحی - Breadth-First Search)** است. در این روش، تمامی حالت‌های ممکن در یک سطح بررسی شده و کوتاه‌ترین مسیر تا رسیدن به پاسخ نهایی انتخاب می‌شود.

### استفاده در هوش مصنوعی و برنامه‌نویسی
این مسئله در زمینه‌های مختلفی از جمله **طراحی الگوریتم‌ها، هوش مصنوعی و منطق ریاضی** به‌عنوان یک مثال کلاسیک مطرح می‌شود. بسیاری از زبان‌های برنامه‌نویسی مانند **پایتون، جاوا و C++** امکان پیاده‌سازی این مسئله را به کمک الگوریتم‌های جستجو و هوش مصنوعی فراهم می‌کنند.

## کاربردهای عملی معما
این معما فراتر از یک بازی فکری است و در **حل مسائل واقعی** نیز کاربرد دارد:

# **هوش مصنوعی و رباتیک**: الگوریتم‌های جستجو در هوش مصنوعی و مسیریابی ربات‌ها از این نوع مسائل الهام گرفته‌اند.
# **برنامه‌ریزی حمل‌ونقل**: در مسائل **بهینه‌سازی مسیر** و **حمل‌ونقل بارهای حساس** (مانند کالاهایی که نباید کنار هم قرار بگیرند) استفاده می‌شود.
# **امنیت سایبری و رمزنگاری**: مدل‌های مشابه این معما در طراحی **الگوریتم‌های امنیتی** و **مدیریت دسترسی کاربران** به داده‌ها کاربرد دارند.
# **مدیریت پروژه و تخصیص منابع**: این معما نشان می‌دهد چگونه می‌توان منابع را تحت محدودیت‌ها به‌صورت بهینه تخصیص داد.

## نتیجه‌گیری
معمای **گرگ و گوسفند و کلم** یکی از مسائل کلاسیک تفکر منطقی و حل مسئله است که در علوم مختلف از **هوش مصنوعی** گرفته تا **برنامه‌ریزی و مدیریت منابع** کاربرد دارد. این معما نشان می‌دهد که **حل مسائل با محدودیت‌های مشخص، نیازمند تفکر مرحله‌ای، مدل‌سازی منطقی و استفاده از روش‌های جستجوی بهینه است.** امروزه، این نوع مسائل همچنان در تحقیقات دانشگاهی، برنامه‌نویسی و آموزش مهارت‌های حل مسئله مورد استفاده قرار می‌گیرند.

## منابع

* The wolf-sheep-cabbage problem | https://www.it.uu.se/edu/course/homepage/ai/ht11/Lecture_2/index.html

رده:بازی‌های راهبردی مجرد
رده:بازی‌های ریاضی
رده:بازی‌های فکری