استفاده ی ابزاری از سودوکو

به اقتضای کار جدید باید C++ استفاده کنم اما همیشه Matlab و Delphi کار بوده ام و این یعنی دوباره شروع کرده ام به اده بده کردن با یک زبان جدید، که البته لطف خودش را دارد.

بعد از فاکتوریال بازی حالا می خواستم با کلاس کار کنم (با Class، نه “با کلاس”) و این شد که رفتم سراغ “سودوکو” Sudoku. کدی که نوشتم را اینجا ببینید. دو کلاس Csudokucell و Csudoku دارد و فایلهایی با پسوند in را می خواند و out بیرون می دهد. از دو استراتژی زیر استفاده می کند و تضمینی نیست همیشه پاسخ را پیدا کند:

۱- اگر خانه ای مشخص شده است این مقدار را برای “همسایه” های آن ممنوع کن.

۲- اگر خانه ای هست که در بین همسایگانش تنها گزینه برای داشتن یک عدد است، حتما مقدار این خانه همان عدد است.

استراتژی ِ دیگری سراغ دارید که پیاده کنیم؟

کد ِ فعلی حداقل از پس جدول زیر بر نمی آید (فایل in. ش این یکی است).

sudoku_example_hard.png

پس نوشت: اینجا یک سری استراتژی هست. کسی اهل پیاده کردنشان هست؟

3 نظر

  1. از Divide and conquer استفاده کن.

    ش - بهمن ۳۰, ۱۳۸۷ ۱۰:۱۳ ب.ظ
  2. ایده کلی اینه، از خونه اول خالی شروع کن، نه تا حالت داره. هر حالت خودش یک مساله جدیده، دوباره این مساله جدید رو بخورون به همین کد خودت، تا حلش کنه (با رابطه بازگشتی). زمانی که یک راه حل به تناقض می رسه (عدد تکراری در یک سطر یا ستون یا در یک بخش) کد بازگشتی اون راه حل بدون جواب بسته میشه.

    کمانگیر: ایده ی خوبی ه، اما بعد از این کم کردن ها این کار رو بکنم دیگه؟ چون در غیر اینصورت داریم در عمل تمام فضا رو می گردیم. چاکریم! ایول!

    ش - بهمن ۳۰, ۱۳۸۷ ۱۰:۱۶ ب.ظ
  3. یک ایده هم اینه که از الگوریتم ژنتیک برای پیدا کردن حواب استفاده کنید. در این روش فضای جستچو بصورت تصادفی بررسی میشه و معمولا در زمان مناسبی جواب پیدا میشه.
    البته روشهای دیگری هم هست کانند beam search که می تونید در هر مرحله فضای جستجو را محدود کنید.
    ایده خوبی بود و سعی میکنم در اولین فرصت این برنامه را بنویسم.

    علیرضا عبادت - اردیبهشت ۹, ۱۳۸۸ ۳:۵۷ ق.ظ

برای این نوشته یک نظر بنویسید

Your email is never published nor shared. Required fields are marked *

*

*

Type your comment out: