برنامه حل سودوکو – 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)

۴۱ دیدگاه

نظر خود را بنویسید.

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