این صد وزیر : صد وزیر!
اینم کدش : کد N وزیر!

از روش کوه نوردی یا Hill Climbing استفاده کردم ... این روش خیلی عالی عمل میکنه!
این روش چی میگه؟ کوهنوردی برای مسئله های Minimization و یا Maximization استفاده میشه اینجوری که به هر وضعیت از مسئله یه امتیازی میدیم و هدفمون پیدا کردن وضعیتی با کمترین (یا بیشترین) امتیاز هست. برای مثال تو این مسئله هر وضعیت برابر یک حالت گذاشتن N وزیر در جدول N*Nهست و امتیاز هر وضعیت ( به ازای وضعیت state ، $f(state) $) رو تعریف میکنیم "تعداد جفت وزیر هایی که یکدیگر رو تهدید میکنن". پس هدفمون رسیدن به وضعیت $target$ هست که $f(target) = 0$ .
روش کوهنوردی بسی سادست. اینجوریه :

1. از یک وضعیت رندوم شروع کن
   
2. به بهترین وضعیت همسایه برو (خیلی خیلی حریصانه!)
   
3. اگه وضعیت کنونی از وضعیت قبلی بهتر نبود وضعیت قبلی رو خروجی بده (به قله رسیدیم) وگرنه به خط 2 برو!!
   

همسایه ی یک وضعیت تعریف خاصی نداره و دست خودمونه که چه چیزی باشه. ولی در سرعت رسیدن به جواب تاثیر خیلی مهمی داره. باید یجوری همسایه رو تعریف کنیم که 1) تعداد همسایه ها خیلی زیاد نشه که برنامه کند بشه و 2) خیلی کم نباشه که به هدف دیر برسیم و مهمتر از اون دو تا 3) واقعن احتمالش باشه که ما رو به وضعیت بهتر برسونه.
چرا کوهنوردی؟! برای مثال اگه هر وضعیت 2 همسایه داشته باشه ، ما میتونیم یه نمودار مثل نمودار زیر از وضعیتا درست کنیم که نقطه ها وضعیت هان و خط ها همسایگی رو نشون میدن و ارتفاع برابر امتیاز وضعیت هست :

خیلی واضح نمودار شبیه یه رشته کوه مسخرست. هدفمون رسیدن به اون نقطه قرمزست. کد ما از یک وضعیت رندوم شروع میکنه و بصورت حریصانه کوهنوردی میکنه تا به قله برسه! برای این اسمشو گذاشتن کوهنوردی و برای سوال هایی که تعداد قله های بهینه نسبت به کل قله ها کم نیست (مثل همین N وزیر) بدرد میخوره.

تو کد من همسایه های هر وضعیت وزیر گذاری تعریف شدن وضعیت هایی که با جابجا کردن یک وزیر که مورد تهدید واقع شده بصورت افقی بشون میشه رسید. اینجوری همسایه ها زیاد هستند(از اردر $N^2$) ولی قله ها خیلی محدودند... حالت هایی که با جابجایی یک وزیر نشه بهترشون کرد خیلی کمه، پس احتمال اینکه به جواب نهایی زود برسیم زیاده.

خلاصه اینجوری کار میکنه و تجربه نشون داده که برای $N \le 100$ زیر یک دقیقه جواب میده! $^_^$

http://paste.ubuntu.com/7638417/