قصه: سودوکو

در این قصه

  1. حل سودوکو با زبان پرل
  2. حل سودوکو با پایتون (همین پست)

فهرست مطالب

"حل سودوکو با پایتون"

توجه!

اگر قصد خواندن توضیحات را ندارید می‌توانید مستقیما به بخش کد کامل برنامه در همین صفحه بروید.

مقدمه🔗

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

سودوکو چیست؟🔗

سودوکو یک بازی فکری محبوب بین اقشار مردم است. یک جدول با ۹ سطر و ۹ ستون که مجموعا تعداد ۸۱ خانه را در بر می‌گیرد. تعدادی از این خانه‌ها پر شده است و خانه‌های خالی می‌بایست توسط بازیکن پر شود. علاوه بر ۹ سطر و ۹ ستون که به راحتی قابل مشاهده هستند جدول به ۹ مربع ۳ در ۳ هم تقسیم می شود. سودوکوی زیر را ببینید. چهار گوشه‌ی هر مربع را با علامت + مشخص کرده‌ایم. سعی کنید این ۹ مربع را شناسایی کنید.

+---+---+---+
|4..|...|8.5|
|.3.|...|...|
|...|7..|...|
+---+---+---+
|.2.|...|.6.|
|...|.8.|4..|
|...|.1.|...|
+---+---+---+
|...|6.3|.7.|
|5..|2..|...|
|1.4|...|...|
+---+---+---+

قوانین حل سودوکو🔗

سودوکو باید با ۴ قانون زیر حل شود:

  1. فقط مجاز به استفاده از اعداد ۱ تا ۹ هستیم.
  2. هر عدد در هر سطر فقط باید یک بار تکرار شود.
  3. هر عدد در هر ستون فقط باید یک بار تکرار شود.
  4. هر عدد در هر مربع فقط باید یک بار تکرار شود.

اجرا و تست برنامه در پوسته‌ی پایتون🔗

در اکثر مثال‌ها، متدها را در پوسته پایتون تست کرده و خروجی گرفته‌ام. این کار سریع‌تر است و در هر مرحله می‌توان کنترل دقیقی بر روی وضعیت برنامه داشت. فایل برنامه‌ی من sudoku.py نام دارد و داخل آن کلاسی به نام Sudoku تعریف شده است. برای ایجاد محیط تست کافیست در همان مسیری که فایل پایتون قرار گرفته است یک ترمینال باز و پایتون را اجرا کنید. در پوسته‌ی پایتون کلاس Sudoku را از ماژول sudoku ایمپورت کنید:

python shell
>>> from sudoku import Sudoku

هم اکنون کلاس Sudoku در پوسته تعریف شده است و کافیست از آن object بسازید و متدها را اجرا کنید. برای این کار عجله نکنید و ادامه مقاله را بخوانید تا با متدها و متغیرها آشنا شوید.

فرمت ورودی و روش‌های اجرای برنامه🔗

برنامه‌ی ما که در فایل sudoku.py قرار دارد می‌تواند از فایل‌های قرار گرفته روی دیسک سخت بخواند. همچنین توانایی خواندن از pipe را هم دارد. فایلی تحت عنوان test.txt را در نظر بگیرید که محتوای آن به صورت زیر است:

test.txt
.....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........

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

پس سودوکوهای قابل قبول توسط برنامه‌ی ما باید فرمتی مشابه فایل فوق داشته باشند.

به یاد داشته باشید!

اگر در فایل ورودی یا pipe بیش از یک سودوکو وجود داشته باشد برنامه تمام آن‌ها را یکی پس از دیگری حل می‌کند!

به دو شیوه می‌توان برنامه را فراخواند:

حل از طریق خواندن از فایل🔗

با فرض اینکه سودوکوها در داخل فایل test.txt قرار دارند به سادگی می‌توان نام فایل را از طریق خط فرمان به برنامه ارسال کرد:

SHELL
$ python sudoku.py test.txt
+---+---+---+
|...|..2|...|
|...|.7.|..1|
|7..|3..|.9.|
+---+---+---+
|8..|7..|...|
|.2.|89.|6..|
|.13|..6|...|
+---+---+---+
|.9.|.5.|824|
|...|..8|91.|
|...|...|...|
+---+---+---+
Solved with  1004  moves
+---+---+---+
|659|412|378|
|238|679|451|
|741|385|296|
+---+---+---+
|865|723|149|
|427|891|635|
|913|546|782|
+---+---+---+
|396|157|824|
|574|268|913|
|182|934|567|
+---+---+---+
@@@@@@@@@@@@@
$

حل از طریق خواندن از pipe🔗

در روش دوم محتوای فایل test.txt را از طریق pipe به عنوان ورودی به برنامه‌ی سودوکو ارسال می‌کنیم:

SHELL
$ cat test.txt | python sudoku.py
+---+---+---+
|...|..2|...|
|...|.7.|..1|
|7..|3..|.9.|
+---+---+---+
|8..|7..|...|
|.2.|89.|6..|
|.13|..6|...|
+---+---+---+
|.9.|.5.|824|
|...|..8|91.|
|...|...|...|
+---+---+---+
Solved with  1004  moves
+---+---+---+
|659|412|378|
|238|679|451|
|741|385|296|
+---+---+---+
|865|723|149|
|427|891|635|
|913|546|782|
+---+---+---+
|396|157|824|
|574|268|913|
|182|934|567|
+---+---+---+
@@@@@@@@@@@@@
$

الگوریتم مورد استفاده🔗

  • ابتدا برای تمام خانه‌هایی که خالی هستند لیست اعداد «ممکن» را پیدا می‌کنیم. در این مرحله اعداد «ممکن» برای یک خانه عبارتند از تمامی اعداد ۱ تا ۹ که تا کنون در سطر و ستون و مربع مربوط به آن خانه قرار نگرفته‌اند.

  • وقتی لیست تمام اعداد «ممکن» برای هر خانه را پیدا کردیم، خانه‌ای را پیدا می‌کنیم که اعداد «ممکن» کمتری دارد و کوچک‌ترین عدد «ممکن» را در آن خانه قرار می‌دهیم. سپس دوباره اقدام به بروزرسانی لیست اعداد ممکن برای تمام خانه‌های خالی می‌کنیم و دوباره عمل فوق را انجام می‌دهیم یعنی کوچک‌ترین عدد «ممکن» خانه‌ای که کمترین تعداد اعداد «ممکن» را دارد را در آن خانه قرار می‌دهیم.

  • بعضی اوقات با انتخاب یک عدد، لیست اعداد قابل انتخاب خانه‌ی دیگری خالی می‌شود. این حالت یعنی برنامه راه را اشتباه رفته است. در این صورت باید rollback کنیم و آخرین خانه‌ای را که پر کرده‌ایم خالی کنیم و با عدد ممکنِ دیگری که از عدد قبلی بزرگ تر است پر کنیم.

  • این چرخه تا زمان حل کامل مساله ادامه می‌یابد.

به یاد داشته باشید!

برنامه زمانی حل شده است که هیچ خانه‌ای، لیست اعداد «ممکن» نداشته باشد، به عبارت دیگر تمام خانه‌ها دارای عدد باشند.

توضیحی در مورد ساختمان داده‌ی برنامه🔗

برنامه دارای یک کلاس است که متغیرها و متدهای آن بعضا private و یا public تعریف شده‌اند. به عنوان مثال متغیری به نام __table که حاوی جدول سودوکو است به صورت private تعریف شده و فقط متدهای کلاس حق دسترسی و تغییر محتوای آن را دارند.

نکته

در زبان پایتون هر متغیر یا متد که با ۲ علامت underline شروع شود متغیر یا متد private است. برای مثال __table یک متغیر private است. البته این موضوع فقط یک قرارداد بین برنامه‌نویسان پایتون است و توسط زبان پشتیبانی نمی‌شود!

متغیرها🔗

لیست متغیرهای استفاده شده در برنامه به شرح زیر است:

متغیر __table🔗

یک dictionary است که محتوای ۸۱ خانه‌ی سودوکو و همچنین مقادیر «ممکن» برای خانه‌های خالی را در برمی‌گیرد. اندیس‌های این دیکشنری از عدد ۰ تا ۸۰ است و محتوای هر اندیس یکی از دو حالت زیر خواهد بود:

  1. اگر خانه متناظر در جدول سودوکو مشخص شده باشد، محتوای این اندیس یک عدد Integer از ۱ تا ۹ است.
  2. اگر خانه متناظر در جدول سودوکو خالی باشد محتوای این اندیس یک لیست حاوی اعداد «ممکن» برای این خانه است. بعدا در طی اجرای برنامه، یکی از اعداد این لیست به عنوان مقدار نهایی خانه انتخاب و جایگزین می‌شود.

همانطور که ملاحظه می‌کنید این متغیر private است و تنها متدهای برنامه باید به آن دسترسی داشته باشند و آن را رونویسی کنند.

متغیر __moves🔗

هنگامی که عدد ۱ تا ۹ را برای یک خانه انتخاب می‌کنیم اصطلاحا می‌گوییم یک «حرکت» انجام داده‌ایم. هر «حرکت‌» انجام شده را به صورت یک لیست [entry, value] در این متغیر قرار می‌دهیم و به معنی این است که عدد value در خانه‌ی entry قرار گرفته است. یک مقدار موقتی برای این متغیر می‌تواند به صورت زیر باشد.

__moves = [[2,5],[4,3],[9,8]]

کد بالا نشان می‌دهد که خانه‌ی ۲ با عدد ۵ و خانه‌ی ۴ با عدد ۳ و خانه‌ی ۹ با عدد ۸ پر شده‌اند. آخرین حرکت انجام شده تا این لحظه پر شدن خانه شماره ۹ با عدد ۸ است.

به یاد داشته باشید!

متغیر __moves بسیار مهم است. هنگامی که برنامه در مسیری که برای پیشروی انتخاب کرده است قادر به ادامه حرکت نباشد مجبور به بازگشت و انتخاب مسیر جایگزین است. در این موقعیت از متغیر __moves برای rollback استفاده می‌کند.

متغیر __rindexes🔗

r مخفف row به معنای ردیف می‌باشد. این متغیر یک لیست است که حاوی ۹ لیست می‌باشد. لیست‌ها با اندیس ۰ تا ۸ قابل دسترسی هستند. هر اندیس نمایان‌گر یک سطر جدول سودوکو است و شماره‌ی خانه‌های آن سطر را نگه‌داری می‌کند. به عنوان مثال اندیس خانه‌های سطر سوم جدول سودوکو به صورت زیر در این متغیر ذخیره می‌شود:

__rindexes[2] = [18, 19, 20, 21, 22, 23, 24, 25, 26]

این متغیر یک بار توسط کلاس مقداردهی می‌شود و بارها مورد استفاده قرار می‌گیرد.

متغیر __cindexes🔗

c ابتدای کلمه‌ی column به معنای ستون است. یک لیست که حاوی ۹ لیست است و اندیس‌های آن از ۰ تا ۸ است و هر اندیس نمایان‌گر یک ستون و محتویات هر اندیس شماره‌ی خانه‌های واقع شده در آن ستون است. به عنوان مثال شماره‌ی خانه‌های واقع شده در ستون شماره ۱ به صورت زیر در این متغیر ذخیره می‌شوند.

__cindexes[0] = [0, 9, 18, 27, 36, 45, 54, 63, 72]

به مانند متغیر __rindexes این متغیر نیز فقط یک‌بار مقداردهی شده و بارها مورد استفاده قرار می‌گیرد.

متغیر __gindexes🔗

g ابتدای کلمه‌ی grid است. این لغت را برای هر مربع ۳ در ۳ انتخاب کرده‌ام. این متغیر که یک لیست است خود حاوی ۹ لیست از اندیس ۰ تا ۸ است. هر اندیس نمایان‌گر یک مربع است. محتوای هر اندیس شماره‌ی خانه‌های موجود در آن مربع است. به عنوان مثال شماره خانه‌های واقع شده در مربع شماره ۳ به صورت زیر در این متغیر ذخیره می‌شود:

__gindexes[2] = [6, 7, 8, 15, 16, 17, 24, 25, 26]

این متغیر مانند متغیرهای فوق private است و فقط یک‌بار توسط کلاس مقداردهی شده و بارها استفاده می‌شود.

متغیر __adjacents🔗

یک لیست است که ۸۱ اندیس دارد یعنی به ازای هر خانه یک اندیس. محتوای هر اندیس یک لیست از شماره‌ی خانه‌های مجاور آن خانه در سطر و ستون و مربع متناظر آن است. به عنوان مثال خانه‌ی شماره‌ی ۱ در سطر ۱ و ستون ۱ و مربع ۱ قرار گرفته است. محتوای متغیر __adjacents برای این خانه به صورت زیر است:

__adjacents[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 27, 36, 45, 54, 63, 72]

چرا از این متغیر استفاده می‌کنیم؟

هنگامی که یک عدد را برای یک خانه انتخاب می‌کنیم، این انتخاب فقط بر روی اعداد «ممکن» خانه‌های قرار گرفته در آن سطر و آن ستون و آن مربع تاثیر می‌گذارد و این عدد از لیست اعداد «ممکن» خانه‌های خالی آن سطر و ستون و مربع حذف می‌شود.

پس برای بروزرسانی اعداد «ممکن» خانه‌های خالی فقط کافیست لیست اعداد «ممکنِ» خانه‌های خالیِ مجاورِ خانه‌ی مقدار دهی شده را بروزرسانی کنیم .

متدهای مقدار‌دهنده🔗

متد __setRIndexes🔗

private است و تنها یک‌بار فراخوانی می‌شود. متغیر __rindexes را مقداردهی می‌کند.

متد __setCIndexes🔗

private است و تنها یک‌بار برای مقدار دهی متغیر __cindexes فراخوانی می‌شود.

متد __setGIndexes🔗

private است و فقط یک‌بار برای مقداردهی متغیر __gindexes فراخوانی می‌شود.

متد __setAdjacents🔗

این متد هم به مانند متدهای پیشین private است. فقط یک‌بار برای مقداردهی متغیر __adjacents فراخوانی می‌شود.

متد __entry2RCG🔗

این متد اندیس خانه را به عنوان ورودی می‌گیرد و سطر و ستون و مربعی که خانه در آن قرار گرفته است را به صورت یک دیکشنری بر می‌گرداند. R در نام متد به معنای row و C به معنای column و G به معنای grid است. این متد private تعریف شده و فقط کلاس حق استفاده از آن را دارد.

به طور تجریدی نمونه‌ی ورودی و خروجی آن به صورت زیر است:

python shell
# In yek code vaghee nist!
>>> b = entry2RCG(80)
>>> print(b)
{'c' : 8, 'r': 8, 'g': 8}

متدهای مهم و اصلی🔗

متد setTable🔗

برای تزریق سودوکوی خام (سودوکوی حل نشده) به برنامه استفاده می‌شود. البته توجه داشته باشید در هنگام تعریف object جدید و در متد __init__ نیز امکان معرفی جدول سودوکو به برنامه وجود دارد ولی به هر حال چنانچه قصد حل کردن چند سودوکو به طور پی در پی را داشته باشیم برای اجتناب از ایجاد object های متعدد از کلاس، از این متد برای تغییر جدول سودوکوی فعلی به جدول جدید استفاده می‌کنیم:

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku()
>>> s.setTable(".32.....58..3.....9.428...1...4...39...6...5.....1.....2...67.8.....4....95....6.")
>>> s.printTable()
+---+---+---+
|.32|...|..5|
|8..|3..|...|
|9.4|28.|..1|
+---+---+---+
|...|4..|.39|
|...|6..|.5.|
|...|.1.|...|
+---+---+---+
|.2.|..6|7.8|
|...|..4|...|
|.95|...|.6.|
+---+---+---+

متد printTable🔗

محتویات جدول سودوکو را نمایش می‌دهد. خانه‌هایی که هنوز مقدار خود را نشناخته‌اند به صورت . نشان داده می‌شوند.

یک نمونه خروجی این متد به صورت زیر است. توجه کنید که این بار بر خلاف مثال بالا سودوکو را از طریق تابع constructor به برنامه تزریق کرده‌ایم:

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.printTable()
+---+---+---+
|4..|...|8.5|
|.3.|...|...|
|...|7..|...|
+---+---+---+
|.2.|...|.6.|
|...|.8.|4..|
|...|.1.|...|
+---+---+---+
|...|6.3|.7.|
|5..|2..|...|
|1.4|...|...|
+---+---+---+

متد __prepareForPrint🔗

همان‌طور که می‌دانیم ساختار داده‌ی اصلی ما یک دیکشنری به نام __table است که بعضی خانه‌های آن دارای یک عدد Integer و بعضی دیگر دارای یک لیست به عنوان لیست اعداد «ممکن» برای آن خانه هستند. این متد بر حسب اینکه برای نمایش جدول سودوکو (متد printTable) فراخوانی شود و یا اینکه برای نمایش جدول اعداد «ممکن» هر خانه (متد printPossibleTable) صدا زده شود اطلاعات هر خانه را برای چاپ آماده می‌کند تا مستقیما در تابع فراخوان استفاده شود.

متد findNextMove🔗

موتور محرک برنامه است، به عبارت دیگر الگوریتم مورد استفاده در این متد پیاده‌ شده است. اگر با شمار‌ه‌ی یک خانه فراخوانی شود بهترین حرکت ممکن برای آن خانه را بر می‌گرداند و اگر بدون شماره خانه صدا شود بهترین «حرکت» را از میان کل «حرکت»های ممکن برمی‌گرداند.

نکته‌ی مهم این است که وظیفه‌ی تشخیص حل سودوکو بر عهده‌ی findNextMove است. زمانی سودوکو کاملا حل شده است که در هیچ یک از اندیس‌های متغیر __table هیچ لیستی وجود نداشته باشد. در این حالت متد مقدار [1000, 1000] را بر می‌گرداند که نشان‌دهنده‌ی حل جدول سودوکو است.

نکته‌ی مهم این که در بسیاری از مواقع مسیری که الگوریتم برای حل سودوکو استفاده می‌کند به بن‌بست می‌خورد و دیگر امکان پیشروی ندارد. بنابر این باید از مسیر رفته عقب‌نشینی و مسیر جدیدی انتخاب کنیم. در این حالت findNextMove مقدار [-1, -1] را بر می‌گرداند که نشان‌دهنده‌ی وجود بن‌بست و عدم امکان پیشروی است.

فراخوانی این متد بر مبنای الگوریتم برنامه می‌باشد ولی یک نمونه اجرای تستی این متد می‌تواند به صورت زیر باشد:

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku()
>>> s.setTable(".32.....58..3.....9.428...1...4...39...6...5.....1.....2...67.8.....4....95....6.")
>>> s.printPossibleTable()
+---------------------------+---------------------------+---------------------------+
|   167*      3        2    |   197*    9467*     197*  |  8946*    8947*      5    |
|    8      1567*     167*  |    3      45679*   1597*  |  9246*    9247*    2467*  |
|    9       567*      4    |    2        8       57*   |   36*       7*       1    |
+---------------------------+---------------------------+---------------------------+
|  12567*   15678*   8167*  |    4       257*    8257*  |  8126*      3        9    |
|  12347*   8147*    13789* |    6      9237*    23789* |  8124*      5       247*  |
| 234567*   45678*   36789* |  8957*      1     235789* |  8246*    8247*    2467*  |
+---------------------------+---------------------------+---------------------------+
|   134*      2       13*   |   159*     935*      6    |    7       149*      8    |
|  1367*    8167*    13678* |  15789*   23579*     4    |  12359*    129*     23*   |
|  1347*      9        5    |   817*     237*    12378* |  1234*      6       234*  |
+---------------------------+---------------------------+---------------------------+
>>> s.findNextMove(0)
[0, 1]
>>> s.findNextMove(3)
[3, 1]
>>> s.findNextMove()
[25, 7]

در مثال بالا بعد از تزریق سودوکوی خام به برنامه توسط متد setTable ابتدا با printPossibleTable لیست اعداد ممکن برای هر خانه را به دست می‌آوریم. سپس با استفاده از متد findNextMove بهترین حرکت بعدی برای خانه‌های شماره‌ی ۱ و ۴ را پیدا می‌کنیم. از روی جدولی که ابتدا بر روی صفحه چاپ کردیم می‌توانید این موضوع را بررسی کنید. در دستور بعدی، متد findNextMove را بدون آرگومان صدا می‌زنیم. در این حالت این متد بهترین حرکت در میان کل خانه‌ها را بر می‌گرداند. از روی جدول بالا می‌توانید ببینید که خانه‌ی شماره ۲۶ تنها یک انتخاب دارد و آن هم عدد ۷ است. لذا یقینا و بدون شک این انتخاب بهترین گزینه است.

توجه

در بسیاری از زبان‌های برنامه‌نویسی اندیس آرایه‌ها و لیست‌ها از ۰ شروع می‌شود. در زبان طبیعی (اینجا فارسی) خانه‌ی شماره ۰ نمی‌گوییم بلکه به طور معمول می‌گوییم خانه‌ی شماره‌ی ۱. لذا وقتی مثلا می‌گوییم خانه‌ی ۲۶ در واقع منظورمان اندیس ۲۵ از لیست مربوطه است. به عنوان مثال دیگر خانه‌ی شماره ۴ دارای اندیس ۳ در یک لیست فرضی است.

متد __updatePossibleTable🔗

برای بروزرسانی لیست اعداد «ممکن» خانه‌های خالی استفاده می‌شود. این متد متغیر __table را بروزرسانی می‌کند. تابع findNextMove بر مبنای اطلاعات فراهم شده توسط این متد بهترین حرکت را انجام می‌دهد.

متد rollback🔗

هنگامی که متد findNextMove تشخیص داد که در مسیر فعلی به بن‌بست خورده‌ایم، تابع rollback را فرامی‌خوانیم. این تابع آخرین حرکت ثبت شده در متغیر __moves (شماره‌ی خانه و مقدار قرارگرفته در آن) را حذف می‌کند و سپس تابع move را به گونه‌ای فرامی‌خواند که مقدار خانه مورد نظر را با لیست خالی پر کند.

متد move🔗

کلیه‌ی حرکت‌ها توسط این متد انجام می‌شود. دو پارامتر ورودی اصلی دارد یکی entry و دیگری value و به این معنی است که مقدار value را داخل خانه‌ی شماره entry قرار می‌دهد. این متد بعد از هر «حرکت» متد __updatePossibleTable را برای بروزرسانی اعداد «ممکن» خانه‌های خالی صدا می‌زند.

مثال در متد getMoves

متد solve🔗

برای حل سودوکو باید چند دستور را پشت سر هم اجرا کنیم. این دستورات را اجمالا در بخش الگوریتم مورد استفاده توضیح دادیم. تعداد دفعاتی که این دستورها باید اجرا شوند مشخص نیست لذا مجموعه‌ی دستورها را داخل یک حلقه while بی‌نهایت قرار می‌دهیم و این کاری است که در متد solve پیاده شده است. وقتی کنترل از این حلقه خارج شود سودوکو حل شده است.

مثال زیر به خوبی این مطلب را بیان می‌کند:

python shell
>>> from sudoku import Sudoku
>>> s.setTable('.5..9....1.....6.....3.8.....8.4...9514.......3....2..........4.8...6..77..15..6.')
>>> s.printTable()
+---+---+---+
|.5.|.9.|...|
|1..|...|6..|
|...|3.8|...|
+---+---+---+
|..8|.4.|..9|
|514|...|...|
|.3.|...|2..|
+---+---+---+
|...|...|..4|
|.8.|..6|..7|
|7..|15.|.6.|
+---+---+---+
>>> s.solve()
>>> s.printTable()
+---+---+---+
|856|491|372|
|143|572|698|
|927|368|451|
+---+---+---+
|278|645|139|
|514|923|786|
|639|817|245|
+---+---+---+
|361|789|524|
|485|236|917|
|792|154|863|
+---+---+---+

متدهای مفید ولی بی‌تاثیر در حل مساله🔗

متد printPossibleTable🔗

جدول سودوکو را نمایش می‌دهد ولی به جای نشان دادن خانه‌های خالی با .، این بار لیست اعداد «ممکن» برای آن خانه‌ها را نمایش می‌دهد. این متد در روند حل سودوکو تاثیری ندارد و فقط یک حالت تصویری برای فهم دقیق‌تر مساله فراهم می‌کند. یک نمونه خروجی این متد می‌تواند به صورت زیر باشد:

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.printPossibleTable()
+---------------------------+---------------------------+---------------------------+
|    4      1967*    12679* |   139*    9236*    1269*  |    8      1239*      5    |
|  26789*     3     1256789*|  14589*   24569*  1245689*|  12679*   1249*   124679* |
|  8926*    15689*  125689* |    7     234569*  1245689*|  12369*   12349*  123469* |
+---------------------------+---------------------------+---------------------------+
|  8937*      2     135789* |  9345*    34579*   9457*  |  13579*     6      13789* |
|  9367*    15679*  135679* |   935*      8      25679* |    4      12359*   12379* |
|  36789*  456789*  356789* |  9345*      1     245679* |  23579*   23589*   23789* |
+---------------------------+---------------------------+---------------------------+
|   892*     89*      892*  |    6       945*      3    |  1259*      7      12489* |
|    5      8967*    36789* |    2       947*    14789* |  1369*    13489*  134689* |
|    1      8967*      4    |   895*     957*    8957*  |  23569*   23589*   23689* |
+---------------------------+---------------------------+---------------------------+

علامت * در بالای بعضی خانه‌ها نشان‌دهنده‌ی این است که آن خانه هنوز مقدار خود را نشناخته و اعداد لیست شده، اعداد «ممکن» آن خانه هستند.

متد getCount🔗

تعداد حرکت‌های انجام شده تا زمان فراخوانی را بر‌می‌گرداند.

متد getMoves🔗

لیست «حرکت‌»های انجام شده را بر می‌گرداند. «حرکت‌»ها در داخل متغیر __moves که یک لیست است ذخیره شده‌اند. این متغیر شامل تعدادی لیست است. اندیس اول هر لیست شماره‌ی خانه و اندیس دوم، مقدار استفاده شده برای آن خانه است. این متد نقشی در حل مساله ندارد و صرفا برای دسترسی به متغیر private نوشته شده است.

نمونه کاربرد این متد را در زیر مشاهده می‌کنید:

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.printTable()
+---+---+---+
|4..|...|8.5|
|.3.|...|...|
|...|7..|...|
+---+---+---+
|.2.|...|.6.|
|...|.8.|4..|
|...|.1.|...|
+---+---+---+
|...|6.3|.7.|
|5..|2..|...|
|1.4|...|...|
+---+---+---+
>>> s.move(1, 5)
>>> s.move(2, 6)
>>> s.getMoves()
[[1, 5], [2, 6]]

متد markEntries🔗

متد نمایشی و بی‌ربط به حل مساله است. در هنگام نوشتن برنامه برای تست مقادیر متغیرهایی نظیر __rindexes و __adjacents مجبور به کنترل تعداد زیادی عدد بودم که کار طاقت‌فرسا و نامطمئنی بود. این متد لیستی از اعداد ۰ تا ۸۰، متناظر با یک جدول سودوکو را می‌گیرد و خانه‌ی متناظر با آن اعداد در جدول سودوکو را با علامت X مشخص می‌کند.

به مثال زیر توجه کنید. می‌خواهیم ببینیم آیا برنامه خانه‌های مجاور خانه‌ی شماره ۰ در جدول سودوکو را درست محاسبه کرده است یا نه:

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.markEntries(s.getAdjacents(0))
+---+---+---+
|xxx|xxx|xxx|
|xxx|   |   |
|xxx|   |   |
+---+---+---+
|x  |   |   |
|x  |   |   |
|x  |   |   |
+---+---+---+
|x  |   |   |
|x  |   |   |
|x  |   |   |
+---+---+---+

متد getRIndexes🔗

نقشی در حل مساله ندارد و صرفا برای دسترسی به محتویات متغیر __rindexes تعریف شده است. شماره‌ای بین ۰ تا ۸ که نمایانگر شماره سطر در جدول سودوکو است را گرفته و شماره‌ی خانه‌های قرار گرفته در آن سطر را بر می‌گرداند.

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

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.getRIndexes(8)
[72, 73, 74, 75, 76, 77, 78, 79, 80]

متد getCIndexes🔗

این متد هم نقشی در حل مساله ندارد و صرفا جهت دسترسی به محتویات متغیر __cindexes تعریف شده است. یک عدد بین ۰ تا ۸ به عنوان شماره ستون می‌گیرد و اندیس خانه‌های قرار گرفته در آن ستون را بر می‌گرداند.

کد زیر شماره‌ی خانه‌های قرار گرفته در ستون اول جدول سودوکو را نشان می‌دهد.

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.getCIndexes(0)
[0, 9, 18, 27, 36, 45, 54, 63, 72]

متد getGIndexes🔗

به مانند تمام متدهای این برنامه که با get شروع می‌شوند، این متد هم نقشی در حل مساله ندارد و برای دسترسی به محتویات متغیر __gindexes نوشته شده است. تکه کد زیر شماره‌ی خانه‌های واقع شده در دومین مربع جدول سودوکو را برمی‌گرداند.

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> s.getGIndexes(1)
[3, 4, 5, 12, 13, 14, 21, 22, 23]

متد getAdjacents🔗

متد دیگری جهت دسترسی به محتوای یک متغیر private است. این متد عددی بین ۰ تا ۸۰ که نمایانگر اندیس یک خانه در جدول سودوکو است را می‌گیرد و اندیس خانه‌های مجاور آن خانه را بر می‌گرداند. این متد نقشی در حل مساله ندارد و صرفا جهت دسترسی به اطلاعات است.

در مثال زیر از متد markEntries برای نمایش بصری لیست خانه‌ها استفاده کرده‌ایم. این کار دید بهتری از اتفاقی که می‌افتد به ما می‌دهد.

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
>>> t = s.getAdjacents(80)
>>> t
[8, 17, 26, 35, 44, 53, 60, 61, 62, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80]
>>> s.markEntries(t)
+---+---+---+
|   |   |  x|
|   |   |  x|
|   |   |  x|
+---+---+---+
|   |   |  x|
|   |   |  x|
|   |   |  x|
+---+---+---+
|   |   |xxx|
|   |   |xxx|
|xxx|xxx|xxx|
+---+---+---+

متد getSampleSudoku🔗

متد ساده‌ای است که یک نمونه سودوکو را برمی‌گرداند. از این متد در نمایش پیغام خطای «فرمت اشتباه سودوکوی ورودی» استفاده کرده‌ام.

python shell
>>> from sudoku import Sudoku
>>> s = Sudoku("4.....8.5.3..........7......2.....6.....8.4......")
Sudoku is not valid
Try something like:  52...6.........7.13...........4..8..6......5...........418.........3..2...87.....

تعدادی سودوکوی نمونه برای تست🔗

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

top95.txt
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
52...6.........7.13...........4..8..6......5...........418.........3..2...87.....
6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....
48.3............71.2.......7.5....6....2..8.............1.76...3.....4......5....
....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
6.2.5.........3.4..........43...8....1....2........7..5..27...........81...6.....
.524.........7.1..............8.2...3.....6...9.5.....1.6.3...........897........
6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....
.923.........8.1...........1.7.4...........658.........6.5.2...4.....7.....9.....
6..3.2....5.....1..........7.26............543.........8.15........4.2........7..
.6.5.1.9.1...9..539....7....4.8...7.......5.8.817.5.3.....5.2............76..8...
..5...987.4..5...1..7......2...48....9.1.....6..2.....3..6..2.......9.7.......5..
3.6.7...........518.........1.4.5...7.....6.....2......2.....4.....8.3.....5.....
1.....3.8.7.4..............2.3.1...........958.........5.6...7.....8.2...4.......
6..3.2....4.....1..........7.26............543.........8.15........4.2........7..
....3..9....2....1.5.9..............1.2.8.4.6.8.5...2..75......4.1..6..3.....4.6.
45.....3....8.1....9...........5..9.2..7.....8.........1..4..........7.2...6..8..
.237....68...6.59.9.....7......4.97.3.7.96..2.........5..47.........2....8.......
..84...3....3.....9....157479...8........7..514.....2...9.6...2.5....4......9..56
.98.1....2......6.............3.2.5..84.........6.........4.8.93..5...........1..
..247..58..............1.4.....2...9528.9.4....9...1.........3.3....75..685..2...
4.....8.5.3..........7......2.....6.....5.4......1.......6.3.7.5..2.....1.9......
.2.3......63.....58.......15....9.3....7........1....8.879..26......6.7...6..7..4
1.....7.9.4...72..8.........7..1..6.3.......5.6..4..2.........8..53...7.7.2....46
4.....3.....8.2......7........1...8734.......6........5...6........1.4...82......
.......71.2.8........4.3...7...6..5....2..3..9........6...7.....8....4......5....
6..3.2....4.....8..........7.26............543.........8.15........8.2........7..
.47.8...1............6..7..6....357......5....1..6....28..4.....9.1...4.....2.69.
......8.17..2........5.6......7...5..1....3...8.......5......2..4..8....6...3....
38.6.......9.......2..3.51......5....3..1..6....4......17.5..8.......9.......7.32
...5...........5.697.....2...48.2...25.1...3..8..3.........4.7..13.5..9..2...31..
.2.......3.5.62..9.68...3...5..........64.8.2..47..9....3.....1.....6...17.43....
.8..4....3......1........2...5...4.69..1..8..2...........3.9....6....5.....2.....
..8.9.1...6.5...2......6....3.1.7.5.........9..4...3...5....2...7...3.8.2..7....4
4.....5.8.3..........7......2.....6.....5.8......1.......6.3.7.5..2.....1.8......
1.....3.8.6.4..............2.3.1...........958.........5.6...7.....8.2...4.......
1....6.8..64..........4...7....9.6...7.4..5..5...7.1...5....32.3....8...4........
249.6...3.3....2..8.......5.....6......2......1..4.82..9.5..7....4.....1.7...3...
...8....9.873...4.6..7.......85..97...........43..75.......3....3...145.4....2..1
...5.1....9....8...6.......4.1..........7..9........3.8.....1.5...2..4.....36....
......8.16..2........7.5......6...2..1....3...8.......2......7..3..8....5...4....
.476...5.8.3.....2.....9......8.5..6...1.....6.24......78...51...6....4..9...4..7
.....7.95.....1...86..2.....2..73..85......6...3..49..3.5...41724................
.4.5.....8...9..3..76.2.....146..........9..7.....36....1..4.5..6......3..71..2..
.834.........7..5...........4.1.8..........27...3.....2.6.5....5.....8........1..
..9.....3.....9...7.....5.6..65..4.....3......28......3..75.6..6...........12.3.8
.26.39......6....19.....7.......4..9.5....2....85.....3..2..9..4....762.........4
2.3.8....8..7...........1...6.5.7...4......3....1............82.5....6...1.......
6..3.2....1.....5..........7.26............843.........8.15........8.2........7..
1.....9...64..1.7..7..4.......3.....3.89..5....7....2.....6.7.9.....4.1....129.3.
.........9......84.623...5....6...453...1...6...9...7....1.....4.5..2....3.8....9
.2....5938..5..46.94..6...8..2.3.....6..8.73.7..2.........4.38..7....6..........5
9.4..5...25.6..1..31......8.7...9...4..26......147....7.......2...3..8.6.4.....9.
...52.....9...3..4......7...1.....4..8..453..6...1...87.2........8....32.4..8..1.
53..2.9...24.3..5...9..........1.827...7.........981.............64....91.2.5.43.
1....786...7..8.1.8..2....9........24...1......9..5...6.8..........5.9.......93.4
....5...11......7..6.....8......4.....9.1.3.....596.2..8..62..7..7......3.5.7.2..
.47.2....8....1....3....9.2.....5...6..81..5.....4.....7....3.4...9...1.4..27.8..
......94.....9...53....5.7..8.4..1..463...........7.8.8..7.....7......28.5.26....
.2......6....41.....78....1......7....37.....6..412....1..74..5..8.5..7......39..
1.....3.8.6.4..............2.3.1...........758.........7.5...6.....8.2...4.......
2....1.9..1..3.7..9..8...2.......85..6.4.........7...3.2.3...6....5.....1.9...2.5
..7..8.....6.2.3...3......9.1..5..6.....1.....7.9....2........4.83..4...26....51.
...36....85.......9.4..8........68.........17..9..45...1.5...6.4....9..2.....3...
34.6.......7.......2..8.57......5....7..1..2....4......36.2..1.......9.......7.82
......4.18..2........6.7......8...6..4....3...1.......6......2..5..1....7...3....
.4..5..67...1...4....2.....1..8..3........2...6...........4..5.3.....8..2........
.......4...2..4..1.7..5..9...3..7....4..6....6..1..8...2....1..85.9...6.....8...3
8..7....4.5....6............3.97...8....43..5....2.9....6......2...6...7.71..83.2
.8...4.5....7..3............1..85...6.....2......4....3.26............417........
....7..8...6...5...2...3.61.1...7..2..8..534.2..9.......2......58...6.3.4...1....
......8.16..2........7.5......6...2..1....3...8.......2......7..4..8....5...3....
.2..........6....3.74.8.........3..2.8..4..1.6..5.........1.78.5....9..........4.
.52..68.......7.2.......6....48..9..2..41......1.....8..61..38.....9...63..6..1.9
....1.78.5....9..........4..2..........6....3.74.8.........3..2.8..4..1.6..5.....
1.......3.6.3..7...7...5..121.7...9...7........8.1..2....8.64....9.2..6....4.....
4...7.1....19.46.5.....1......7....2..2.3....847..6....14...8.6.2....3..6...9....
......8.17..2........5.6......7...5..1....3...8.......5......2..3..8....6...4....
963......1....8......2.5....4.8......1....7......3..257......3...9.2.4.7......9..
15.3......7..4.2....4.72.....8.........9..1.8.1..8.79......38...........6....7423
..........5724...98....947...9..3...5..9..12...3.1.9...6....25....56.....7......6
....75....1..2.....4...3...5.....3.2...8...1.......6.....1..48.2........7........
6.....7.3.4.8.................5.4.8.7..2.....1.3.......2.....5.....7.9......1....
....6...4..6.3....1..4..5.77.....8.5...8.....6.8....9...2.9....4....32....97..1..
.32.....58..3.....9.428...1...4...39...6...5.....1.....2...67.8.....4....95....6.
...5.3.......6.7..5.8....1636..2.......4.1.......3...567....2.8..4.7.......2..5..
.5.3.7.4.1.........3.......5.8.3.61....8..5.9.6..1........4...6...6927....2...9..
..5..8..18......9.......78....4.....64....9......53..2.6.........138..5....9.714.
..........72.6.1....51...82.8...13..4.........37.9..1.....238..5.4..9.........79.
...658.....4......12............96.7...3..5....2.8...3..19..8..3.6.....4....473..
.2.3.......6..8.9.83.5........2...8.7.9..5........6..4.......1...1...4.22..7..8.9
.5..9....1.....6.....3.8.....8.4...9514.......3....2..........4.8...6..77..15..6.
.....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........
3...8.......7....51..............36...2..4....7...........6.13..452...........8..

کد کامل برنامه🔗

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

SHELL
$ cat sudoku.py | sed '/^#/d;/^[ \t]*#/d;/^$/d' | wc
    220     818    8024

کد کامل برنامه را از کادر زیر دریافت کنید:

sudoku.py
#
# Sudoku solver with python
# --------------------------------------
# programmer: Mohsen Safari
# email: safari.tafreshi@gmail.com
# website: dokaj.ir
# --------------------------------------
#
# Sorry for my bad english (Lo siento mucho por mi ingles!)
#
import sys
import fileinput

class Sudoku:
    # number of moves for resolving this sudoku
    __count = 0

    # self.__table is a dictionary and contains values or
    # possibilidades of each entry
    __table = {}

    # self.__move keeps track of each move
    #is neccessary for Rollback!
    __moves = []

    # a sample sudoku. no has any role in problem solving!
    __sampleSudoku = "52...6.........7.13...........4..8..6......5...........418.........3..2...87....."

    # define (and after in codes: set)  row indexes, column indexes, grid indexes
    __rindexes = [[], [], [], [], [], [], [], [], []]
    __cindexes = [[], [], [], [], [], [], [], [], []]
    __gindexes = [[], [], [], [], [], [], [], [], []]

    # variable for keep entries adjacents of each entry
    __adjacents = []

    def __init__(self, table = None):
        # create one list for each entry. contents of each list will be adjacents
        # of that entry
        for i in range(81):
            self.__adjacents.append([])

        # set values: row indexes, column indexes, grid indexes, adjacents
        self.__setRIndexes()
        self.__setCIndexes()
        self.__setGIndexes()
        self.__setAdjacents()

        # create sudoku table with information provided in table
        if table is not None:
            try:
                self.setTable(table)
            except SyntaxError:
                print("Sudoku is not valid")
                print("Try something like: ", self.getSampleSudoku())

    # create sudoku table 
    def setTable(self, table):
        self.__count = 0
        self.__moves = []
        self.__table = {}

        if len(str(table)) != 81:
            raise SyntaxError

        # read sudoku table and set in self.table
        for i in range(len(table)):
            # if value is not specified fill its place with
            # empty list. this list will be filled with
            # all numbers possible
            if table[i] == ".":
                self.__table[i] = []
            else :
                self.__table[i] = int(table[i])

        # update possible values for each entry which no has value
        self.__updatePossibleTable(fullUpdate = True)

    # set row indexes for each row. key is row number and values are
    # number of each entry inside that row
    # Example:
    # self.__rindexes[0] = [0,1,2,3,4,5,6,7,8] ,
    # self.__rindexes[1] = [9,10,11,12,13,14,15,16,17]
    def __setRIndexes(self):
        for i in range(9):
            s = i * 9
            for j in range(9):
                self.__rindexes[i].append(s + j)

    # set column indexes for each column. key is column number and values are
    # number of each each entry inside that column
    # example:
    # self.__cindexes[0] = [0,9,18,27,36,45,54,63,72]
    def __setCIndexes(self):
        for i in range(9):
            c = i % 9
            self.__cindexes[i].append(c)
            for j in range(8):
                c = c + 9
                self.__cindexes[i].append(c)

    # set grid indexes for each grid. key is grid number and values are
    # number of each entry inside that grid
    # example:
    # self.__gindexs[0] = [0,1,2,9,10,11,18,19,20]
    def __setGIndexes(self):
        gStartIndexes = [0, 3, 6, 27, 30, 33, 54, 57, 60]

        for i in range(9):
            s = gStartIndexes[i]
            self.__gindexes[i].append(s)
            self.__gindexes[i].append(s + 1)
            self.__gindexes[i].append(s + 2)
            self.__gindexes[i].append(s + 9)
            self.__gindexes[i].append(s + 10)
            self.__gindexes[i].append(s + 11)
            self.__gindexes[i].append(s + 18)
            self.__gindexes[i].append(s + 19)
            self.__gindexes[i].append(s + 20)

    # set all neighbors for each entry. key is number of entry
    # and values are numbers of each entry in this row and this
    # column and this grid
    # example:
    # self.__adjacents[0] = [0,1,2,3,4,5,6,7,8,9,18,27,36,45,54,63,72,10,11,19,20]
    def __setAdjacents(self):
        for i in range(81):
            tmp = self.__entry2RCG(i)
            self.__adjacents[i] = list(set(self.__rindexes[tmp["r"]] + self.__cindexes[tmp["c"]] + self.__gindexes[tmp["g"]]))


    # get i'th row indexes of __rindexes.
    # just is a getter and no has any role in problem solving
    def getRIndexes(self, i):
        return self.__rindexes[int(i)]

    # get i'th column indexes of __cindexes
    # just a getter and no has any role in problem solving
    def getCIndexes(self, i):
        return self.__cindexes[int(i)]

    # get i'th grid indexes of __gindexes
    # just a getter and no has any role in problem solving
    def getGIndexes(self, i):
        return self.__gindexes[int(i)]

    # get all adjacents of one index
    # just a getter and no has any role in problem solving
    def getAdjacents(self, i):
        return self.__adjacents[int(i)]


    # return a sample sudoku.
    # this sample is just forpresentation of input format and no has 
    # and role in problem solving
    def getSampleSudoku(self):
        return self.__sampleSudoku


    # get entry and find its row, its column and its grid
    # example: entry2RCG(11)--->row:1, column:2, grid:0
    # Already only used inside the "setAdjacents" methos
    def __entry2RCG(self, entry):
        r = int(entry / 9)
        c = entry % 9

        if r <= 2 :
            g = 0 if c <= 2 else 1 if c <= 5 else 2
        elif r <= 5:
            g = 3 if c <= 2 else 4 if c <= 5 else 5
        else :
            g = 6 if c <= 2 else 7 if c <= 5 else 8

        return {'c':c, 'r':r, 'g':g}


    # prepare variable self.table for print on screen
    def __prepareForPrint(self, removeList = True, space = 1):
        tmp = {}
        for i in range(len(self.__table)):
            if type(self.__table[i]) == list and removeList:
                tmp[i] = "."
            elif type(self.__table[i]) == list:
                tmp[i] = (''.join(str(x) for x in self.__table[i]) + "*").center(space)
            else:
                tmp[i] = str(self.__table[i]).center(space)

        return tmp


    # print sudoko table. those entries that no have value will be displayed with a "."
    # Example:
    # We have this sudoko:
    # ..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..
    #
    # method "printTable" will have this output:
    # +---+---+---+
    # |..5|3..|...|
    # |8..|...|.2.|
    # |.7.|.1.|5..|
    # +---+---+---+
    # |4..|..5|3..|
    # |.1.|.7.|..6|
    # |..3|2..|.8.|
    # +---+---+---+
    # |.6.|5..|..9|
    # |..4|...|.3.|
    # |...|..9|7..|
    # +---+---+---+
    def printTable(self):
        tmp = self.__prepareForPrint()

        for i in list(map(lambda x: x[0], self.__rindexes)):
            if i % 27 == 0:
                print("+---+---+---+")

            print(
                    "|" + tmp[i+0] + tmp[i+1] + tmp[i+2] + \
                    "|" + tmp[i+3] + tmp[i+4] + tmp[i+5] + \
                    "|" + tmp[i+6] + tmp[i+7] + tmp[i+8] + "|"
            )

        print("+---+---+---+")


    # print possible table
    # for above sudoku output the printPossibleTable will be:
    # +---------------------------+---------------------------+---------------------------+
    # |  1269*     924*      5    |    3      24689*   24678* |  14689*   14679*   8147*  |
    # |    8       934*     169*  |  9467*    9456*     467*  |  1469*      2      1347*  |
    # |  9236*      7       926*  |  8946*      1      8246*  |    5       946*     834*  |
    # +---------------------------+---------------------------+---------------------------+
    # |    4       892*    26789* |  8169*     896*      5    |    3       197*     127*  |
    # |   925*      1       892*  |   894*      7       834*  |   924*     945*      6    |
    # |  9567*     95*       3    |    2       946*     146*  |   149*      8      1457*  |
    # +---------------------------+---------------------------+---------------------------+
    # |  1237*      6      8127*  |    5      8234*   123478* |  8124*     14*       9    |
    # |  12579*   8925*      4    |  8167*     826*    12678* |  8126*      3      8125*  |
    # |  1235*    8235*     812*  |  8146*    23468*     9    |    7      1456*    12458* |
    # +---------------------------+---------------------------+---------------------------+
    def printPossibleTable(self):
        space = 9
        tmp = self.__prepareForPrint(False, space)

        for i in list(map(lambda x: x[0], self.__rindexes)):
            if i % 27 == 0:
                print( ("+" + ("-" * space) * 3) * 3 + "+")

            print(
                    "|" + tmp[i+0] + tmp[i+1] + tmp[i+2] + \
                    "|" + tmp[i+3] + tmp[i+4] + tmp[i+5] + \
                    "|" + tmp[i+6] + tmp[i+7] + tmp[i+8] + "|"
            )

        print( ("+" + ("-" * space) * 3) * 3 + "+")


    # only find next best move. return entry and its finded value.
    # if variable "entry" is set then find best move for that entry
    # when no more move is possible return [-1, -1]
    # this value means that we have to RollBACK!
    # if each entry has its value return [1000, 1000]
    # this value means that sudoku is already solved.
    def findNextMove(self, entry = -1):
        count, minLength = 0, 1000

        if [] in self.__table.values():
            return [-1, -1]

        if entry != -1:
            tmp = sorted(self.__table[entry])
            if not len(tmp):
                return [-1, -1]
            return [entry, tmp[0]]


        for k, v in self.__table.items():
            if type(v) == list :
                count = count + 1
                if len(v) < minLength:
                    minLength = len(v)
                    entry = k


        if count == 0:
            return [1000, 1000]

        tmp = sorted(self.__table[entry])
        value = tmp[0]
        return [entry, value]


    # delete last move and call "updatepossibleTable()"
    def rollback(self):
        move = self.__moves.pop()
        entry, value = move[0], move[1]
        self.move(entry, [], value)
        return entry 

    # a getter for __count variable
    # no has any role in problem solving
    def getCount(self):
        return self.__count

    # get entry and value and set value in that entry
    def move(self, entry, value, onRollBackValueGreaterThan = -1):
        self.__table[entry] = value
        self.__count = self.__count + 1

        if type(value) != list:
            self.__moves.append([entry, value])

        if value == []:
            self.__updatePossibleTable(entry, onRollBackValueGreaterThan, fullUpdate = True)
        else:
            self.__updatePossibleTable(entry, onRollBackValueGreaterThan)


    # get moves variable
    # just a getter. no has any role in problem solving
    def getMoves(self):
        return self.__moves

    # update possible table
    # normally we call this function after each move and each rollback
    def __updatePossibleTable(self, entry = -1, valueGreaterThan = -1, fullUpdate = False):
        values = set()

        if fullUpdate == True:
            check = range(81)
        elif entry != -1:
            check = self.__adjacents[entry]
        else:
            print("Unknown update policy")
            sys.exit(1)

        for i in check:
            if type(self.__table[i]) != list:
                continue

            values.clear()
            for j in self.__adjacents[i]:
                if type(self.__table[j]) == list:
                    continue
                values.add(self.__table[j])

            possibles = list({1,2,3,4,5,6,7,8,9} - values)
            if i == entry:
                possibles = list(filter(lambda x: x > valueGreaterThan, possibles))

            self.__table[i] = possibles

    def markEntries(self, indexes):
        for i in range(9):
            start = i * 9

            if i % 3 == 0:
                print("+---+---+---+")

            for j in range(9):
                if j % 3 == 0:
                    print("|", end="")
                if (start + j) in indexes:
                    print("x", end="")
                else:
                    print(" ", end="")
            print("|")

        print("+---+---+---+")

    # solve sudoku by repeating these steps
    # 1- find best move or roll back last move
    # 2- move
    # go to step 1 
    def solve(self):
        # reset number of tries for resolving this sudoku
        self.__count = 0

        entry = -1
        # while true ...
        while(True):
            # find next move. if entry is set "findNextMove" will find next
            # value for specified entry
            entry, value = self.findNextMove(entry)

            # if we have no more moves and sudoku is solved then break
            if entry == 1000 and value == 1000:
                return  

            # last move is incorrect. Rollback!
            if entry == -1:
                entry = self.rollback()
                continue

            # set finded value in its entry
            self.move(entry, value)
            entry = -1


    def __repr__(self):
        return "another sudoku solver with python!"


if __name__ == "__main__" :
    # create object of sudoku with sudoku of user
    obj = Sudoku()

    # read sudoku from standard input or file
    # format of sudoku has to be similar:
    # ..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..
    for line in fileinput.input():
        string = line.rstrip()

        try:
            obj.setTable(string)
        except SyntaxError:
            print("Sudoku is not valid")
            print("Try something like: ", obj.getSampleSudoku())
            continue

        # print sudoku on screen
        obj.printTable()

        # solve sudoku
        obj.solve()

        # Already sudoku is solved
        print("Solved with ", obj.getCount(), " moves")

        # Display solved sudoku
        obj.printTable()
        print("@@@@@@@@@@@@@")
نوشته شده در: 1402-02-10 (1 سال 7 ماه 6 روز پیش)

من محسن هستم؛ برنامه‌نویس سابق PHP و Laravel و Zend Framework و پایتون و فلسک. تمرکزم بیشتر روی لاراول بود! الان از صفر مشغول مطالعات اقتصادی هستم.

برای ارتباط با من یا در همین سایت کامنت بگذارید و یا به dokaj.ir(at)gmail.com ایمیل بزنید.

در مورد این مطلب یادداشتی بنویسید.