الگوریتم‌های عقبگرد

معمای هشت وزیر از جمله مسائل کلاسیک مباحث طراحی الگوریتم است که در حالت کلی‌تر با عنوان معمای n وزیر یا معمای چند وزیر مطرح می‌شود.

برای افرادی که با بازی شطرنج آشنایی ندارند

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

معمای n وزیر

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