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

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

یک جواب نمونه برای مسئله‌ی 8 وزیر

چندین نکته‌ی مهم در حل این مسئله وجود دارد که باید به آنها توجه کرد. یکی از این موارد نحوه‌ی نمایاندن جواب مساله است یعنی ساخت یک جواب هرچند این جواب مورد قبول نباشد. بعبارت دیگر چگونه نشان دهیم که کدام وزیر در کدام خانه قرار دارد. در ساده ترین شکل ممکن می‌توان از یک آرایه‌ی دو بعدی 8 در 8 برای هر یک از خانه‌های صفحه‌ی شطرنج استفاده کرد. اگر وزیری در هر یک از خانه‌ها قرار بگیرد، مقدار آن خانه را برابر 1 درغیر این‌صورت برابر 0 درنظر می‌گیریم. اگر از نوع داده‌ی int استفاده کنیم باتوجه به این‌که هر خانه 4 بایت فضا اشغال می‌کند، در مجموع 8 × 8 × 4 Bytes = 256 Bytes فضا لازم داریم. با یک حساب سرانگشتی معلوم می‌شود که برای مشخص کردن مختصات 8 وزیر استفاده از 256 بایت، نوعی اتلاف حافظه بشمار می‌رود. حتی استفاده از نوع داده‌ای Boolean که به یک بایت فضا نیاز دارد، در مجموع 64 بایت را اشغال می‌کند.

با کمی بهبود، می‌توان آرایه‌ای 8 عنصری برای نگهداری شماره‌ی سطر و ستون وزیرهای جایگذارای شده در نظر گرفت. یعنی برای هر وزیر از دو عدد صحیح برای مشخص کردن شماره‌ی سطر و ستون استفاده کنیم. در این حالت 8 × 2 × 4 Bytes = 64 Bytes بایت فضا لازم داریم. برای جواب نمونه‌ی شکل بالا آرایه‌ای که جواب را نشان می‌دهد بصورت زیر است.

int Queens[8][2];
Queens[0][0] = 0; Queens[0][1] = 4;
Queens[1][0] = 1; Queens[1][1] = 1;
Queens[2][0] = 2; Queens[2][1] = 3;
Queens[3][0] = 3; Queens[3][1] = 6;
Queens[4][0] = 4; Queens[4][1] = 2;
Queens[5][0] = 5; Queens[5][1] = 7;
Queens[6][0] = 6; Queens[6][1] = 5;
Queens[7][0] = 7; Queens[7][1] = 0;

البته ذکر این نکته هم ضروری است که در این نگرش، صفحه‌ی شطرنج با اندیس‌های زیر در نظر گرفته شده است:

در بُعد دوم آرایه، برای هر خانه با اندیس i مولفه‌ی اول (i₀) بیانگر شماره سطر و مولفه‌ی دوم (i₁) بیانگر شماره ستون وزیر iاُم می‌باشد. بیان جواب مسئله به این شکل اخیر نیز قابل بهبود است. اگر توجه داشته باشید، مقدار i₀ همواره برابر مقدار i است و از اینرو نیازی به ذخیره‌ی آن نیست. این بهبود از این واقعیت نشات می‌گیرد که در همه‌ی جوابهای قابل قبول برای این مسئله، فقط و فقط یک وزیر در هر سطر وجود دارد (در غیر اینصورت دو وزیری که در یک سطر قرار دارند به همدیگر گارد خواهند داد).
پس برای نمایش یک جواب قابل قبول برای مسئله، اینگونه می‌گوییم که آرایه‌ی تک بُعدی با 8 خانه (بُردار 8 تایی) را تعریف کرده و شماره‌ی ستون وزیری که در سطر iاُم قرار دارد را در خانه‌ی iاُم ثبت می‌کنیم. حالا در حالتی بهبنه تر از روش‌های قبلی، جواب مسئله در 32 بایت فضا ذخیره می‌شود. در برنامه‌هایی که در ادامه ارائه خواهد شد، از این حالت اخیر برای نمایاندن جواب‌ها استفاده خواهیم کرد.

حال به سراغ حل مسئله می‌رویم. ابتدا اجازه دهید با 8 حلقه تکرار تودرتو که هریک از آن‌ها نماینده‌ی یک سطر است شروع کنیم. هریک از حلقه‌ها ستون‌های 8 گانه‌ی آن سطر را مرور می‌کند. اگر وزیری که می‌خواهیم در سطر و ستون جاری قرار دهیم با سایر وزیرهایی که قبلا جایگذاری شده برخوردی داشته باشد (فراخوانی تابع Check())، از آن خانه عبور می‌کنیم و وزیر را در آن خانه قرار نمی‌دهیم. اما اگر جایگذاری با موفقیت انجام شود، به سراغ سطر بعدی و جایگذاری وزیر مربوط به آن سطر می‌رویم.
اگر با مرور همه‌ی خانه‌های یک سطر امکان جایگذاری وزیر وجود نداشته باشد، معلوم می‌شود که وزیر سطر قبلی (و شاید سطرهای قبل تر) در جای مناسبی قرار نگرفته‌اند، لذا جای آن را عوض کرده و مجدداً به سراغ سطرهای بعدی می‌رویم. تکرار این فرآیند باعث جایگذاری صحیح هر 8 وزیر می‌شود. در درس «طراحی الگوریتم‌ها» این روش جستجوی کامل فضای حالت برای تولید جواب‌ها به «رویکرد عقبگرد (Backtracking)» معروف است و یافتن جواب‌های مورد قبول در کل فضای حالت «رویکرد شاخه و قید (Branch and bound)» است که با حذف حالت‌هایی که منجر به تولید جواب قابل قبول نمی‌شوند بدست می‌آید. معمولا الگوریتم‌های پیمایشی در طیفی مابین این دو رویکرد قرار دارند.

با جایگذاری موفق آخرین وزیر به یک حالت پایدار می‌رسیم و بعنوان جواب قابل قبول آن را در خروجی چاپ می‌کنیم. بعد از یافتن یک جواب، حلقه‌های تکرار را تا آخر ادامه می‌دهیم و سعی می‌کنیم همه‌ی حالت‌های ممکن برای چیدمان 8 وزیر را بدست بیاوریم.

نکته‌ی مهم دیگری که در حل این مسئله وجود دارد تشخیص برخورد (گارد وزیرها) است و برای این کار تابعی بنام Check() نوشته شده و در همه‌ی برنامه‌هایی که در ادامه مطرح می‌شود از این تابع استفاده می‌کنیم:

bool Check(int Board[], int i) {
  for (int j = i - 1; j >= 0; j--)
    if (Board[i] == Board[j] || abs(i - j) == abs(Board[i] - Board[j]))
      return false;
  return true;
}

برنامه‌ی 8 وزیر با استفاده از تابع Check() و حلقه‌های تودرتو بشکل زیر خواهد بود. البته خواهید دید که کارایی این روش برای nهای بزرگ بسیار پایین است.

void main() {
  int Board[8], c = 0, i0, i1, i2, i3, i4, i5, i6, i7, j;
  for (i0 = 0; i0 < 8; i0++) {
    Board[0] = i0;
    for (i1 = 0; i1 < 8; i1++) {
      Board[1] = i1;
      if (Check(Board, 1))
        for (i2 = 0; i2 < 8; i2++) {
          Board[2] = i2;
          if (Check(Board, 2))
            for (i3 = 0; i3 < 8; i3++) {
              Board[3] = i3;
              if (Check(Board, 3))
                for (i4 = 0; i4 < 8; i4++) {
                  Board[4] = i4;
                  if (Check(Board, 4))
                    for (i5 = 0; i5 < 8; i5++) {
                      Board[5] = i5;
                      if (Check(Board, 5))
                        for (i6 = 0; i6 < 8; i6++) {
                          Board[6] = i6;
                          if (Check(Board, 6))
                            for (i7 = 0; i7 < 8; i7++) {
                              Board[7] = i7;
                              if (Check(Board, 7)) {
                                cout << ++c << ": ";
                                for (j = 0; j < 8; j++)
                                  cout << Board[j] << " ";
                                cout << endl;
                              }
                            }
                        }
                    }
                }
            }
        }
    }
  }
}