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

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

و اما الگوریتم حل کردن سودوکو  به شرح زیر است:

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

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

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

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

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

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

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

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

 

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