ورود به سایت

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

ثبت نام ×

لطفا فرم را پر کرده و ثبت نام کنید!

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

فهرست مطالب [ پنهان کردن ]
مقدمه
سودوکو چیست
قوانین حل سودوکو
اجرا و تست برنامه در پوسته‌ی پایتون
فرمت ورودی و روش‌های اجرای برنامه
     حل از طریق فایل
     حل از طریق خواندن از pipe
الگوریتم مورد استفاده
توضیحی در مورد ساختمان داده‌ی برنامه
متغیرها
     متغیر __table
     متغیر __moves
     متغیر __rindexes
     متغیر __cindexes
     متغیر __gindexes
     متغیر __adjacents
متدهای مقدار‌دهنده
     متد __setRIndexes
     متد __setCIndexes
     متد __setGIndexes
     متد __setAdjacents
     متد __entry2RCG
متدهای مهم و اصلی
     متد setTable
     متد printTable
     متد __prepareForPrint
     متد findNextMove
     متد __updatePossibleTable
     متد rollback
     متد move
     متد solve
متدهای مفید ولی بی‌تاثیر در حل مساله
     متد printPossibleTable
     متد getCount
     متد getMoves
     متد markEntries
     متد getRIndexes
     متد getCIndexes
     متد getGIndexes
     متد getAdjacents
     متد getSampleSudoku
تعدادی سودوکوی نمونه برای تست
کد کامل برنامه
مطالب مرتبط

مقدمه

توجه!

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

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

سودوکو چیست

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

سودوکوی زیر را ببینید. چهار گوشه‌ی هر مربع را با علامت + مشخص کرده‌ایم. سعی کنید ۹ مربع را شناسایی کنید.

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

 

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

سودوکو باید با ۳ قانون زیر حل شود:
  • فقط مجاز به استفاده از اعداد 1 تا 9 هستیم.
  • هر عدد در هر سطر فقط باید یک‌بار تکرار شود.
  • هر عدد در هر ستون فقط باید یک‌بار تکرار شود.
  • هر عدد در هر مربع فقط باید یک‌بار تکرار شود.

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

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

Python
>>> from sudoku import Sudoku
>>>

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

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

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

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

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

پس فایل فوق دارای یک سودوکو است.

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

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

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

حل از طریق فایل

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

Bash
$ 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 به عنوان ورودی به برنامه‌ی سودوکو ارسال می‌کنیم.

Bash
$ 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|
+---+---+---+
@@@@@@@@@@@@@
$

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

  • ابتدا برای تمام خانه‌هایی که خالی هستند لیست اعداد «ممکن» را پیدا می‌کنیم. در این مرحله اعداد «ممکن» برای یک خانه عبارتند از تمامی اعداد 1 تا 9 که تاکنون در سطر و ستون و مربع مربوط به آن خانه قرار نگرفته‌اند.
  • وقتی لیست تمام اعداد «ممکن» برای هر خانه را پیدا کردیم، خانه‌ای را پیدا می‌کنیم که اعداد «ممکن» کمتری دارد و کوچک‌ترین عدد «ممکن» را در آن خانه قرار می‌دهیم. و سپس دوباره اقدام به بروزرسانی لیست اعداد ممکن برای تمام خانه‌های خالی می‌کنیم و دوباره عمل فوق را انجام می‌دهیم یعنی کوچک‌ترین عدد «ممکن» خانه‌ای که کمترین تعداد اعداد «ممکن» را دارد را در آن خانه قرار می‌دهیم.
  • بعضی اوقات با انتخاب یک عدد، لیست اعداد قابل انتخاب خانه‌ی دیگری خالی می‌شود. یعنی برنامه راه را اشتباه رفته است. در این صورت باید rollback کنیم و آخرین خانه‌ای را که پر کرده‌ایم خالی کنیم و با عدد محتمل دیگری که از عدد قبلی بزرگت‌تر است پر کنیم.
  • این چرخه تا زمان حل کامل مساله ادامه می‌یابد.

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

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

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

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

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

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

متغیرها

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

متغیر __table

یک dictionary است که محتوای ۸۱ خانه‌ی سودوکو و همچنین مقادیر «ممکن» برای خانه‌های خالی را در برمی‌گیرد. اندیس‌های این دیکشنری از عدد ۰ تا ۸۰ است و محتوای هر اندیس یکی از دو حالت زیر خواهد بود:
  • اگر خانه متناظر در جدول سودوکو مشخص شده باشد، محتوای این اندیس یک عدد Integer از ۱ تا ۹ است.
  • اگر خانه متناظر در جدول سودوکو خالی باشد محتوای این اندیس یک لیست حاوی اعداد «ممکن» برای این خانه است. بعدا در طی اجرای برنامه، یکی از اعداد این لیست به عنوان مقدار نهایی خانه انتخاب و جایگزین می‌شود.
همانطور که ملاحظه می‌کنید این متغیر private است و تنها متدهای برنامه قادر به دسترسی مستقیم و رونویسی آن هستند.

متغیر __moves

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

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

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

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

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

متغیر __rindexes

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

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

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

متغیر __cindexes

c ابتدای کلمه‌ی column به معنای ستون است. یک لیست که حاوی 9 لیست است و اندیس‌های آن از 0 تا 8 است و هر اندیس نمایانگر یک ستون و محتویات هر اندیس شماره‌ی خانه‌های واقع شده در آن ستون است. به عنوان مثال شماره‌ی خانه‌های واقع شده در ستون شماره 1 به صورت زیر در این متغیر ذخیره می‌شوند.

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

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

متغیر __gindexes

g ابتدای کلمه‌ی grid است. این لغت را برای هر مربع 3 در 3 انتخاب کرده‌ام. این متغیر که یک لیست است خود حاوی 9 لیست از اندیس 0 تا 8 می‌باشد. هر اندیس نمایان‌گر یک مربع است. محتوای هر اندیس شماره‌ی خانه‌های موجود در آن مربع است. به عنوان مثال شماره خانه‌های واقع شده در مربع شماره 3 به صورت زیر در این متغیر ذخیره می‌شود:

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

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

متغیر __adjacents

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

Text
__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 را مقداردهی می‌کند. (پرش به توضیحات متغیر __rindexes)

متد __setCIndexes

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

متد __setGIndexes

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

متد __setAdjacents

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

متد __entry2RCG

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

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

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

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

متد setTable

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

Python
>>> 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

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

Python
>>> 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
>>> 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.|
+---+---+---+
>>> s.move(0, 1)
>>> s.move(80, 2)
>>> s.printTable()
+---+---+---+
|132|...|..5|
|8..|3..|...|
|9.4|28.|..1|
+---+---+---+
|...|4..|.39|
|...|6..|.5.|
|...|.1.|...|
+---+---+---+
|.2.|..6|7.8|
|...|..4|...|
|.95|...|.62|
+---+---+---+

در مثال بالا بعد از تزریق سودوکوی خام به برنامه در خانه‌ی اندیس 0 یعنی اولین خانه عدد 1 و در خانه‌ی اندیس 80 یعنی آخرین خانه عدد 2 را قرار می‌دهیم. سپس جدول را با تابع printTable نمایش می‌دهیم. می‌توانید صحت عملیات را از روی جدول تصدیق کنید.

متد __updatePossibleTable

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

متد rollback

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

متد move

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

متد solve

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

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

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

متد printPossibleTable

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

Python
>>> 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
>>> 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 مجبور به کنترل تعداد زیادی عدد بودم که کار طاقت‌فرسا و نامطمئنی بود. این متد لیستی از اعداد 0 تا 80، متناظر با یک جدول سودوکو را می‌گیرد و خانه‌ی متناظر با آن اعداد در جدول سودوکو را با علامت x مشخص می‌کند. به مثال زیر توجه کنید.

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

Python
>>> 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 تعریف شده است. شماره‌ای بین 0 تا 8 که نمایانگر شماره سطر در جدول سودوکو است را گرفته و شماره‌ی خانه‌های قرار گرفته در آن سطر را بر می‌گرداند.

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

Python
>>> 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 تعریف شده است. یک عدد بین 0 تا 8 به عنوان شماره ستون می‌گیرد و اندیس خانه‌های قرار گرفته در آن ستون را بر می‌گرداند.

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

Python
>>> 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
>>> 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 است. این متد عددی بین 0 تا 80 که نمایانگر اندیس یک خانه در جدول سودوکو است را می‌گیرد و اندیس خانه‌های مجاور آن خانه را بر می‌گرداند. این متد نقشی در حل مساله ندارد و صرفا جهت دسترسی به اطلاعات است.

Python
>>> 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
>>> 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.....

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

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

Text
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..

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

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

Python
#
# Sudoku solver with python
# --------------------------------------
# programmer: Mohsen Safari
# Mobile phone : +989355071859
# email: safari.tafreshi@gmail.com
# --------------------------------------
#
# 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, entry, value = 0, 1000, -1, -1
 
		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("@@@@@@@@@@@@@")

مطالب مرتبط


نظر شما



 
 
 
لینک‌های مفید