«معمای گورخر» یک معمای منطقی مشهور است که در آن پنج خانه وجود دارد و هر خانه به رنگ متفاوتی درآمده است. ساکنان این خانهها با هم فرق دارند: هر کدام ملیت متفاوتی دارند، حیوان خانگی متفاوتی نگه میدارند، نوشیدنی متفاوتی مینوشند و برند سیگار متفاوتی میکشند.
برای اینکه بتوانید این معما را حل کنید، ۱۵ گزاره در اختیارتان قرار میگیرد که راهحل را توصیف میکنند. با این حال، تنها با ترکیب اطلاعات همهی این گزارهها میتوانید راهحل معما را پیدا کنید.
معمای گورخر یک مسئلهی ارضای محدودیت (CSP) است. در چنین مسئلهای، مجموعهای از مقادیر ممکن دارید و مجموعهای از محدودیتها که تعیین میکنند کدام مقادیر معتبرند. یکی دیگر از مسائل مشهور ارضای محدودیت، سودوکو است.
وظیفهی شما حل معمای گورخر است تا پاسخ این دو پرسش را پیدا کنید:
۱۵ گزارهی زیر همگی درست هستند:
علاوه بر این، هر یک از پنج خانه به رنگ متفاوتی رنگ شده است. ساکنان آنها ملیتهای متفاوتی دارند، حیوان خانگی متفاوتی نگه میدارند، نوشیدنی متفاوتی مینوشند و برند سیگار متفاوتی میکشند.
۲۴ میلیارد (5!⁵ = 24,883,200,000) راهحل ممکن وجود دارد، پس سعی کنید تا جای ممکن راهحلهای بیشتری را حذف کنید.
در Exercism ثبتنام کنید تا Nim را همراه با 70 تمرین و مربیگری انسانی واقعی یاد بگیرید و در آن استاد شوید، همهی اینها رایگان.
۸ روش متفاوت برای یافتن پاسخ معمای گورخر از میان ۲۴ میلیارد راهحل ممکن را بررسی کنید؛ از جمله کنار گذاشتن جایگشتهای نامعتبر به محض امکان، الگوریتم AC-3، یک راهحل بسیار کوتاه مبتنی بر منطق و حتی یک الگوریتم ژنتیک!