Missionaries and cannibals problem
مشنریوں اور کینبلوں کا مسئلہ، اور قریب سے متعلق حسد کرنے والے شوہروں کا مسئلہ، دریا کو عبور کرنے والی کلاسیکی منطق پہیلیاں ہیں۔ مشنریوں اور کینبلوں کا مسئلہ مصنوعی ذہانت میں کھلونوں کا ایک معروف مسئلہ ہے، جہاں اسے ساؤل امرل نے مسئلہ کی نمائندگی کی مثال کے طور پر استعمال کیا تھا۔ مشنریوں اور کینبلوں کے مسئلے میں، تین مشنریوں اور تین کینبلوں کو ایک کشتی کا استعمال کرتے ہوئے دریا عبور کرنا پڑتا ہے جو زیادہ سے زیادہ دو افراد کو لے جا سکتی ہے، اس رکاوٹ کے تحت کہ دونوں کناروں کے لیے، اگر کنارے پر مشنری موجود ہوں تو ان کی تعداد کینبلوں سے زیادہ نہیں ہو سکتی (اگر وہ ہوتے تو کینبلیں مشنریوں کو کھا جاتے)۔ کشتی بغیر کسی شخص کے دریا کو اکیلے عبور نہیں کر سکتی۔ اور، کچھ تغیرات میں، کینبلز میں سے ایک کا صرف ایک بازو ہوتا ہے اور وہ قطار نہیں بنا سکتا۔ حسد کرنے والے شوہر کے مسئلے میں، مشنری اور کینبل تین شادی شدہ جوڑے بن جاتے ہیں، اس پابندی کے ساتھ کہ کوئی بھی عورت دوسرے مرد کی موجودگی میں نہیں ہو سکتی جب تک کہ اس کا شوہر بھی موجود نہ ہو۔ اس رکاوٹ کے تحت، بینک میں خواتین اور مرد دونوں موجود نہیں ہو سکتے جن کی تعداد مردوں سے زیادہ ہو، کیونکہ اگر ہوتی تو یہ خواتین اپنے شوہروں کے بغیر ہوتیں۔ لہذا، مردوں کو مشنری اور خواتین کو کینبل میں تبدیل کرنے پر، حسد کرنے والے شوہر کے مسئلے کا کوئی بھی حل بھی مشنریوں اور کینبل کے مسئلے کا حل بن جائے گا۔ مشنریوں اور کینبلوں کے مسئلے کو حل کرنے کے لیے ایک ایسا نظام جس کے تحت موجودہ ریاست کی نمائندگی ایک سادہ ویکٹر کے ذریعے کی جاتی ہے۔ ویکٹر کے عناصر مشنریوں، کینبلوں کی تعداد کی نمائندگی کرتے ہیں، اور یہ کہ آیا کشتی بالترتیب غلط طرف ہے۔ چونکہ کشتی اور تمام مشنری اور کینبل غلط سمت سے شروع ہوتے ہیں، اس لیے ویکٹر کو 75 3,3,1  आहात سے شروع کیا جاتا ہے۔ ریاستی ویکٹر کو جوڑنے کے لیے ویکٹر گھٹاؤ/اضافے کا استعمال کرتے ہوئے اعمال کی نمائندگی کی جاتی ہے۔ مثال کے طور پر، اگر کوئی تنہا کینبل دریا کو عبور کرتا ہے، تو ویکٹر 75 0,1,1  आहात کو ریاست سے گھٹا کر حاصل کیا جائے گا۔ ریاست اس بات کی عکاسی کرے گی کہ ابھی بھی تین مشنری اور دو کینبل غلط سمت میں ہیں، اور یہ کہ کشتی اب مخالف کنارے پر ہے۔ مسئلے کو مکمل طور پر حل کرنے کے لیے، ایک سادہ درخت بنایا جاتا ہے جس کی ابتدائی حالت جڑ ہوتی ہے۔ اس کے بعد پانچ ممکنہ اعمال (अमلو 1,0,1 ایل او،  امولو 2,0,1 ایل او،  امولو 0,1,1 ایل او،  امولو 0,2,1 ایل او، اور  امولو 1,1,1 ایل او) کو ابتدائی حالت سے گھٹا دیا جاتا ہے، جس کے نتیجے میں جڑ کے چلڈرن نوڈس بنتے ہیں۔ کوئی بھی نوڈ جس کے دونوں کناروں پر مشنریوں سے زیادہ کینبل ہیں وہ غلط حالت میں ہے، اور اس لیے اسے مزید غور سے ہٹا دیا جاتا ہے۔ پیدا ہونے والے بچوں کے درست نوڈس अमلو 3,2,0 ایل او،  املو 3,1,0 ایل او، اور  املو 2,2,0 ایل او ہوں گے۔ ان بقیہ نوڈس میں سے ہر ایک کے لیے، بچوں کے نوڈس ہر ممکنہ ایکشن ویکٹر کو شامل کرکے تیار کیے جاتے ہیں۔ الگورتھم درخت کی ہر سطح کے لیے باری باری گھٹاؤ اور اضافہ جاری رکھتا ہے یہاں تک کہ ایک نوڈ پیدا ہو جاتا ہے جس میں ویکٹر 75 0,0,0  आहात اس کی قیمت ہوتی ہے۔ یہ ہدف کی حالت ہے، اور درخت کی جڑ سے اس نوڈ تک کا راستہ ان اعمال کے سلسلے کی نمائندگی کرتا ہے جو مسئلہ کو حل کرتے ہیں۔ حسد کرنے والے شوہر کے مسئلے کا ابتدائی حل، 11 یک طرفہ دوروں کا استعمال کرتے ہوئے، مندرجہ ذیل ہے۔ شادی شدہ جوڑوں کو α (مرد) اور a (عورت)، β اور b، اور γ اور c کے طور پر پیش کیا جاتا ہے۔، صفحہ 291۔ یہ مسئلہ کا مختصر ترین حل ہے، لیکن یہ واحد مختصر ترین حل نہیں ہے۔، صفحہ 291۔ اگر تاہم، ایک وقت میں صرف ایک آدمی کشتی سے باہر نکل سکتا ہے اور شوہروں کو ساحل پر اپنی بیوی کے ساتھ شمار کرنے کے لیے ساحل پر ہونا چاہیے جیسا کہ صرف ساحل پر کشتی میں ہونے کے برخلاف: 5 سے 6 تک منتقل ہونا ناممکن ہے، کیونکہ جیسے ہی γ ساحل پر قدم رکھتا ہے b اپنے شوہر کے ساتھ نہیں ہوگا، اس کے باوجود کہ وہ صرف کشتی میں ہے۔ جیسا کہ پہلے ذکر کیا گیا ہے، حسد کرنے والے شوہروں کے مسئلے کا یہ حل مشنریوں اور नरभक्षیوں کے مسئلے کا حل بن جائے گا جب مردوں کی جگہ مشنری اور خواتین کی جگہ नरभक्षیوں کو لایا جائے گا۔ اس صورت میں ہم مشنریوں اور کینبلوں کی انفرادی شناخت کو نظر انداز کر سکتے ہیں۔ ابھی دیا گیا حل اب بھی مختصر ترین ہے، اور چار مختصر ترین حلوں میں سے ایک ہے۔ اگر ساحل پر کشتی میں کوئی عورت (لیکن ساحل پر نہیں) اکیلی شمار ہوتی ہے (یعنی۔ ساحل پر کسی آدمی کی موجودگی میں نہیں)، پھر اس پہیلی کو 9 یک طرفہ دوروں میں حل کیا جا سکتا ہے: تغیرات ایک واضح عام بات یہ ہے کہ حسد کرنے والے جوڑوں (یا مشنریوں اور کینبلوں) کی تعداد، کشتی کی صلاحیت، یا دونوں میں فرق کرنا ہے۔ اگر کشتی میں 2 افراد ہوتے ہیں، تو 2 جوڑوں کو 5 ٹرپس کی ضرورت ہوتی ہے ؛ 4 یا اس سے زیادہ جوڑوں کے ساتھ، مسئلہ کا کوئی حل نہیں ہے۔ اگر کشتی 3 افراد کو پکڑ سکتی ہے، تو 5 جوڑے پار کر سکتے ہیں ؛ اگر کشتی 4 افراد کو پکڑ سکتی ہے، تو جوڑوں کی کوئی بھی تعداد پار کر سکتی ہے۔، صفحہ 300۔ ان عام فہمیوں کا تجزیہ کرنے اور انہیں حل کرنے کے لیے ایک سادہ گراف تھیوری نقطہ نظر 1966 میں فریلی، کوک اور ڈیٹرک نے دیا تھا۔ اگر دریا کے بیچ میں کوئی جزیرہ شامل کیا جائے تو جوڑے کی کوئی بھی تعداد دو افراد کی کشتی کا استعمال کرتے ہوئے عبور کر سکتی ہے۔ اگر کنارے سے کنارے تک جانے کی اجازت نہیں ہے، تو دریا کے پار n جوڑوں کو لے جانے کے لیے 8n−6 یک طرفہ سفر کی ضرورت ہے۔، صفحہ 76 اگر ان کی اجازت ہے، تو 4n + 1 سفر کی ضرورت ہے اگر n 4 سے زیادہ ہے، حالانکہ کم سے کم حل کے لیے صرف 16 دوروں کی ضرورت ہوتی ہے اگر n 4 کے برابر ہے۔، صفحہ 79۔ اگر حسد کرنے والے جوڑوں کی جگہ مشنری اور کینبل لے لیتے ہیں، اگر بینک سے بینک جانے کی اجازت نہیں ہے تو ضروری دوروں کی تعداد تبدیل نہیں ہوتی ہے۔ تاہم اگر وہ ہیں تو دوروں کی تعداد کم ہو کر 4n−1 ہو جاتی ہے، یہ فرض کرتے ہوئے کہ n کم از کم 3 ہے۔، صفحہ 81۔ حسد کرنے والے شوہروں کے مسئلے کی پہلی معروف ظاہری شکل قرون وسطی کے متن پروپوزیشنز ایڈ ایکیوینڈوس جووینز میں ہے، جسے عام طور پر الکوئن (وفات 804) سے منسوب کیا جاتا ہے۔ الکوئن کی تشکیل میں جوڑے بھائی اور بہن ہیں، لیکن رکاوٹ اب بھی وہی ہے-کوئی بھی عورت دوسرے مرد کی صحبت میں نہیں ہو سکتی جب تک کہ اس کا بھائی موجود نہ ہو۔، صفحہ 74۔ 13 ویں سے 15 ویں صدی تک، یہ مسئلہ پورے شمالی یورپ میں مشہور ہوا، جوڑے اب شوہر اور بیویاں ہیں۔، پی پی۔ اس مسئلے کو بعد میں آقاؤں اور خدمت گاروں کی شکل میں پیش کیا گیا۔ مشنریوں اور کینبلوں کے ساتھ تشکیل 19 ویں صدی کے آخر تک ظاہر نہیں ہوئی۔، پی۔ 81 جوڑوں کی تعداد اور کشتی کے سائز میں فرق 16 ویں صدی کے آغاز میں سمجھا جاتا تھا۔، صفحہ 296۔ کیڈٹ ڈی فونٹینے نے 1879 میں دریا کے بیچ میں ایک جزیرہ رکھنے پر غور کیا۔ دو افراد پر مشتمل کشتی کے ساتھ اس مسئلے کی اس قسم کو 1989 میں ایان پریس مین اور ڈیوڈ سنگ ماسٹر نے مکمل طور پر حل کیا تھا۔ 2020 میں، اس مسئلے کے بارے میں ایک کارٹون میں نسل پرستانہ موضوعات سے متعلق تنازعہ کی وجہ سے اے کیو اے امتحان بورڈ نے اس مسئلے پر مشتمل ایک نصابی کتاب واپس لے لی۔ بھیڑیا، بکری اور گوبھی کا مسئلہ سرکم سکریپشن (منطق) حوالہ جات منطقی پہیلیاں بھی دیکھیں۔