برنامه حل سودوکو – sudoku

SUDOKU

امروز برایتان برنامه حل سودوکو را گذاشته ام .سودوکو یک بازی گیگ پسنده و به طبع آن برنامه حل کننده سودوکو هم بسیار جالب است و نکات آموزشی زیادی دارد.با ما باشید تا برنامه و الگوریتم سودوکو را بررسی کنیم.

اگر نمی دانید سودوکو چیست به این آدرس بروید  (سودوکو در ویکی پدیا)

220px-جدول_سودوکو

 

الگوریتم حل کردن سودوکو:

ابتدا در تمام خانه‌های خالی جدول، اعداد را از یک تا نه می‌نویسیم.

سپس به سراغ یکی از اعدادی که از قبل توسط طراح نوشته شده می‌رویم و تمام اعداد مشابه آن را که در عرضش (بصورت افقی)قرار گرفته‌اند را پاک می‌کنیم و سپس یک خط افقی در بالای آن عدد می‌کشیم که مشخص باشد.

در این مرحله همانند مرحله قبل عمل می‌کنیم با این اختلاف که در تمام خانه‌های عمودی در بالا یا پایین عدد مورد نظر اعداد مشابه را پاک می‌کنیم وسپس با یک خط عمودی در کنار آن عدد آن را مشخص می‌نماییم. اکنون باید اعداد مشابه عدد مورد نظر را در مربع نه خانه‌ای متناظر، پاک کنیم وعدد را با یک دایره بر دور آن مشخص کنیم.

 

فقط سه مرحله قبلی را در مورد تمام اعداد از قبل نوشته شده (اعداد چاپی) تکرار کنیم و کشیدن خطهای عمودی افقی و دایره را بر آن عددها نباید فراموش کنیم که این عمل می‌تواند به شما نشان دهد که کدام یک از قلم افتاده‌است.

وقتی که تمام اعداد چاپی با هر سه علامت مشخص شد کار ما تا این مرحله تمام شده‌است. در این مرحله به دنبال خانه‌هایی می‌گردیم که فقط یک عدد در آنها باقی مانده و آن اعداد را پررنگ می‌کنیم.

ما باید در هر ستون نیز عددی را که فقط یکبار درآن ستون آمده را پیدا کنیم که این عدد یقینا جواب همان خانه‌است و این عدد را هم پررنگ کنیم. اکنون در هر مربع نه خانه‌ای عددی را که فقط یکبار در این نه خانه آمده‌است را یافته و به عنوان جواب یادداشت می‌کنیم.

اگر احساس کردید که روش فوق بسیار وقت گیر و خسته کننده است از روش میانبر زیر استفاده کنید توجه داشته باشید که هر عدد در هر مربع یک بار مصرف می شود و جدول ما دارای نه تا از مجموعه خانه های مربع شکل است سه در سه لذا هر عدد علاوه بر اینکه در هر ردیف وهر ستون یکبار مصرف می شود در هر مربع نیز یک بار مورد استفاده قرار میگیرد پس اگر عددی در یک مربع بزرگ پیدا شد بگردید و نظیر آن عدد را در مربع بزرگ در همان ردیف و یا همان ستون پیدا کنید ، اگر آن را پیدا کردید یک خط فرضی از آن عدد از هر مربع بصورت افقی و یا عمودی بکشید با این کار ۲ ستون و یا دو ردیف از مربعی که عدد در آن نبوده است از محاسبات حذف میشوند و فقط ۳ خانه از آن مربع باقی می ماند ، همین کار را هم از طرف مقابل از همان عدد انجام دهید یک خانه خالی بر جای می ماند که جای همان عدد است . معمولا با این کار بیشتر خانه های خالی پر میشوند که مابقی را از طریق اسکن کردن سطر به سطر و یا ستون به ستون میتوان بدست آورد .

کد هم به همین طریق کار می کند .کد ها به زبان c هستند و comment , codestyle به خوبی رعایت شده است .

روش وارد کردن سوال: ابتدا در پوشه برنامه یک فایل text با نام SUDOKU.TXT باز می کنید و سوال خود را مانند این نمونه در آن وارد می کنید:

 

۹ . . ۷ . . . . ۱
۱ . ۶ . ۴ . . . .
. . . ۹ ۶ . ۷ . ۴
۲ . . . . . ۵ ۹ .
. . ۵ ۲ . ۷ . . .
. ۱ . . . ۵ . ۷ .
. ۳ . . . . ۱ . ۶
. . . . ۳ . . ۸ ۷
. ۲ ۸ . . . . . .

 

این هم جوابی که برنامه به این مثال می ده:

gfgf

 

 

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۴۱ comments

  • برنامه خوبیه ولی برای همه جواب نمیده فقط برای سودکو های ساده جواب میده حتی برای متوسطم جواب نمیده یرای نمونه دوتا سودکو میطارم اولی خیلی سخت
    دومی متوسط از سایت http://jadvalonline.com/sudoko
    ۴ ۳ ۰ ۰ ۶ ۰ ۰ ۰ ۰
    ۰ ۰ ۰ ۸ ۰ ۰ ۰ ۰ ۱
    ۰ ۰ ۰ ۰ ۰ ۰ ۰ ۰ ۰
    ۰ ۷ ۰ ۰ ۰ ۰ ۶ ۳ ۰
    ۵ ۰ ۰ ۰ ۰ ۱ ۰ ۰ ۰
    ۰ ۰ ۰ ۲ ۰ ۰ ۰ ۰ ۰
    ۱ ۰ ۸ ۰ ۰ ۰ ۵ ۰ ۰
    ۰ ۰ ۰ ۰ ۷ ۰ ۰ ۹ ۰
    ۲ ۰ ۰ ۰ ۰ ۰ ۰ ۰ ۰
    دومی متوسط
    ۷ ۰ ۰ ۰ ۰ ۰ ۴ ۰ ۶
    ۰ ۰ ۳ ۹ ۰ ۰ ۰ ۱ ۰
    ۰ ۰ ۵ ۰ ۱ ۸ ۰ ۳ ۰
    ۰ ۰ ۰ ۰ ۰ ۰ ۶ ۴ ۳
    ۰ ۰ ۰ ۸ ۹ ۵ ۰ ۰ ۰
    ۲ ۷ ۱ ۰ ۰ ۰ ۰ ۰ ۰
    ۰ ۳ ۰ ۴ ۶ ۰ ۸ ۰ ۰
    ۰ ۴ ۰ ۰ ۰ ۷ ۲ ۰ ۰
    ۱ ۰ ۷ ۰ ۰ ۰ ۰ ۰ ۴

    • میتونین خودتون با مثال های دیگه چک کنین بازم دستتون درد نکنه

    • فرهاد دلیرانی

      سلام
      بدی روش های سرچ بدون اطلاعات که به صورت کاملا کور به دنبال جواب می گردند دقیقا همینه. ممکنه از ریسورس هایی که اون سیستم در اختیار برنامه قرار می ده بیشتر طلب کنند که باعث قطع اجرای برنامه می شه- یا ممکنه از نظر زمانی برای رسیدن به جواب بیش از حد مورد نیاز زمان ببرند

    • سلام. اونی که خیلی سخت بود رو امتحان کردم بعد از پنج شیش ثانیه حل شد!

  • ببخشید اشتباه شد توی خط های ۹۸ و ۱۰۷ ارور میده به جای isspace(ch) عبارت ch != ‘ ‘ رو هم قرار دادم ولی بازم ارور میده

  • سلام کد برنامه جدول سودوکو به زبان پایتون رو میخوام

  • Pingback: الگوریتم وکد سودوکو

  • چرا با وجود فایل text برای نمونه داده ای ورودی ، خطای input file SUDOKU.TXT does not exist رو اعلام میکنه ؟

    • فرهاد دلیرانی

      چک کن ببین اسم فایل دقیق همان چیزی که گفته شده وارد می کنی یا نه ، با چه کامپایلری نوشتی؟

      • بله اسم فایلم درسته .
        تو dev نوشتم .

        • فرهاد دلیرانی

          چیز خاصی به ذهنم نمی رسه فقط این به ذهنم می رسه :
          فایل مورد نظر رو در تمام پوشه هایی که پروژه ات رو درونش ایجاد کردی کپی کن ، احتمالا دو سه تا پوشس.
          من خودم این با کامپایلر کد بلاک نوشتم و دوباره تست کردم درست بود

  • ببخشید من می خوام این برنامه را با نرم افزار cfree اجرا کنم ممنون ؟

  • سلام این برنامه در کد ۹۸و۱۰۷ گیر میده اگر می شود دوباره چک کنید خواهشمندم دوباره برایم من ایمل کنید . با تشکر ؟

    • فرهاد دلیرانی

      سلام دوباره تست کردم درسته من اینو با کامپایلر
      code::blocks نوشتم ولی احتمالا کامپایلرت به
      isspace(ch) داره گیر می ده بجاش بنویس:
      ch != ‘ ‘

  • برنامتون جواب نمیده

  • سلام
    خسته نباشید
    کد سودوکو رو میشه با رشته و صف و لیست یک پیوندی و دو پیوندی نوشت؟
    اگه میشه راهنماییم کنید

  • سلام.. مهندس این کد رو به زبان C++ اصلاحش کردم ولی کار نمیکنه..
    اگ امکان داره تصحیح شده به زبان C++ رو ایمیل کنید واسم ممنون میشم.

  • سلام
    از چه کامپایلری استفاده کنم ؟

  • سلام
    قطعه کد خط ۷۳ تا ۱۱۰ رو اگه لطف کنید برامون توضیح بدید.
    با تشکر

    • فرهاد دلیرانی

      در قسمت main اطلاعات را از فایل خوانده و در جریان ورودی ریخته در تابع read-grid مقادیر رو از جریان ورودی کاراکتر به کاراکتر می خونه و در آرایه دو بعدی جدول سودوکو می ریزه

  • سلام در مورد برنامه سودوکو سوالاتی داشتم به ایمیل شما ارسال کردم
    لطفا چک کنید

  • سلام
    این برنامه رو میخوام با ویژال سی پلاس پلاس ران کنم
    لطفا راهنمانیم کنید
    نیاز مبرم دارم

    • فرهاد دلیرانی

      تقریبا کار خاصی نمی خواد کیند همینو کپی کنید تو ویژوال استدیو و کامپایل کنید هر جا خطا گرفت معادل سی پلاس پلاسش را بنویسید ۹۰ درصد با سی مشابهت دارد.

  • سلام
    این برنامه با توربو c++ ران میکنم اما دوتا اخطار که
    parameter ‘argv’ and ‘argc’ is never used
    و اینکه به محض ران شدن سریع برمیگرده
    نمیدونم getch() رو کجا قرار بدم
    لطفا راهنمانیم کنید

    • فرهاد دلیرانی

      توربو سی پلاس پلاس خیلی قدیمی ، از کامپایلر کدبلاکس code::blocks یا QT یا visual stdio استفاده کنید .اگه به نمونه برنامه های توریو سی پلاس پلاس نگاه کنید می بینید که جلوی main یه چیزایی نوشته اون ها رو کپی کن و توی پرانتز جلوی مین بزار.آخر مین getch بزار .موقق باشید.

  • می بخسید این فرمان چکار می کند isspace
    موقع اجرا این دستور را نمی شناسد
    فکر می کنم باید کتابختنه خاصی داشته باشه که اضافه نکردم

    • فرهاد دلیرانی

      تابع خود زبان سی باید کار کنه – اگه از ویژوال استدیو استفاده می کنید معدلش رو پیدا کنید یا خودتون بنویسید -چک می کند تا ببیند کاراکتر فاصله است یا نه .

  • من میخواستم در مورد جدول توضیح بدید که من با استاد میخواهیم بحث کنیم

  • مجتبی گودرزی

    سلام فرهاد جان ، خیلی مطلب جالبی بود دست گلت درد نکنه ، منم به احتمال زیاد دانشگاه آی تی یا نرم افزار قبول بشم اگه خواستی می تونم توی مطالبت کمکت کنم
    البته امیدوارم که منو شناخته باشی ، اگه یادت نیومد کی هستم یاداوری این که چند سال پیش با هم المپیاد کامپیوتر رفتیم خرم آباد و کلی خوش گذشت
    با آرزوی بهترین ها
    مُجی !

    • فرهاد دلیرانی

      سلام مجتبی جان , به قول بعضی دوستان “محال خاطرات شمال یادم بره”.خیلی خوشحال می شوم که شما را مدیر سایت کنم البته بیشتر خوشحال می شوم شما رشته مورد علاقتون قبول شوید.باهات از طریق ایمیل ارتباط برقرار می کنم.

  • وبلاگ من رو با عنوان آموزش برنامه نویسی لینک کنید.

  • سلام
    نگفتیدوبلاگتون رو با چه نامی لینک کنم؟

Leave a Reply

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *