+---+---+---+ |4..|...|8.5| |.3.|...|...| |...|7..|...| +---+---+---+ |.2.|...|.6.| |...|.8.|4..| |...|.1.|...| +---+---+---+ |...|6.3|.7.| |5..|2..|...| |1.4|...|...| +---+---+---+
صفحه نخست | سیستم وبلاگ | در مورد من | twitter
توجه!
اگر قصد خواندن توضیحات را ندارید میتوانید مستقیما به بخش دانلود کد پایتون در همین صفحه بروید.قبلا مسالهی سودوکو را با پرل حل کرده بودیم ولی برای تفریح هم که شده تصمیم گرفتم این بار آن را با پایتون حل کنم. به هر حال گمان میکنم پایتون مورد استفادهی طیف گستردهتری از برنامهنویسان و کاربران سیستمهای لینوکس است. الگوریتم مورد استفاده را تغییر ندادم ولی برای اینکه شما را به آن مقاله ارجاع ندهم و از طرفی این مقاله کاملا مستقل باشد کلیهی متدها و ساختار برنامه و نحوهی اجرای آن را شرح خواهم داد.
سودوکوی زیر را ببینید. چهار گوشهی هر مربع را با علامت + مشخص کردهایم. سعی کنید ۹ مربع را شناسایی کنید.
+---+---+---+ |4..|...|8.5| |.3.|...|...| |...|7..|...| +---+---+---+ |.2.|...|.6.| |...|.8.|4..| |...|.1.|...| +---+---+---+ |...|6.3|.7.| |5..|2..|...| |1.4|...|...| +---+---+---+
>>> from sudoku import Sudoku >>>
هم اکنون کلاس Sudoku در پوسته تعریف شده است و کافیست از آن object بسازید و متدها را اجرا کنید. برای این کار عجله نکنید و ادامه مقاله را بخوانید تا با متدها و متغیرها آشنا شوید.
.....2.......7...17..3...9.8..7......2.89.6...13..6....9..5.824.....891..........
هر خط نشاندهندهی یک سودوکو است، یعنی اگر سودوکوی دومی وجود میداشت باید آن را در خط بعد وارد میکردیم. خانههای خالی که مقدار آن باید توسط بازیکن پیدا شود توسط یک دات . علامتگذاری شده است.
پس فایل فوق دارای یک سودوکو است.
به یاد داشته باشید!
اگر در فایل ورودی یا pipe بیش از یک سودوکو وجود داشته باشد برنامه تمام آنها را یکی پس از دیگری حل میکند!به دو شیوه میتوان برنامه را فراخوانی کرد:
$ 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| +---+---+---+ @@@@@@@@@@@@@ $
$ 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| +---+---+---+ @@@@@@@@@@@@@ $
به یاد داشته باشید!
برنامه زمانی حل شده است که هیچ خانهای، لیست اعداد محتمل نداشته باشد، به عبارت دیگر تمام خانهها دارای عدد باشند.به یاد داشته باشید!
در زبان پایتون هر متغیر یا متد که با ۲ علامت underline شروع شود متغیر یا متد private است. برای مثال متغیر __table یک متغیر private است.__moves = [[2,5],[4,3],[9,8]]
کد بالا نشان میدهد که خانهی ۲ با عدد ۵ و خانهی ۴ با عدد ۳ و خانهی ۹ با عدد ۸ پر شدهاند. آخرین حرکت انجام شده تا این لحظه پر شدن خانه شماره 9 با عدد 8 است.
به یاد داشته باشید!
متغییر __moves بسیار مهم است. هنگامی که برنامه در مسیری که برای پیشروی انتخاب کرده است قادر به ادامه حرکت نباشد مجبور به بازگشت و انتخاب مسیر جایگزین است. در این موقعیت از متغیر __moves برای rollback استفاده میکند.__rindexes[2] = [18, 19, 20, 21, 22, 23, 24, 25, 26]
این متغیر یک بار توسط کلاس مقداردهی میشود و بارها مورد استفاده قرار میگیرد.
__cindexes[0] = [0, 9, 18, 27, 36, 45, 54, 63, 72]
به مانند متغیر __rindexes این متغیر نیز فقط یکبار مقداردهی شده و بارها مورد استفاده قرار میگیرد.
__gindexes[2] = [6, 7, 8, 15, 16, 17, 24, 25, 26]
این متغیر مانند متغیرهای فوق private است و فقط یکبار توسط کلاس مقداردهی شده و بارها استفاده میشود.
__adjacents[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 20, 27, 36, 45, 54, 63, 72]
به یاد داشته باشید!
چرا از این متغیر استفاده میکنیم؟ هنگامی که یک عدد را برای یک خانه انتخاب میکنیم، این انتخاب فقط بر روی اعداد «ممکن» خانههای قرار گرفته در آن سطر و آن ستون و آن مربع تاثیر میگذارد و از لیست اعداد «ممکن» خانههای خالی آن سطر و ستون و مربع حذف میشود. پس برای بروزرسانی اعداد «ممکن» خانههای خالی فقط کافیست احتمالات خانههای خالی مجاور آن خانه را بروزرسانی کنیم .به طور تجریدی نمونهی ورودی و خروجی آن به صورت زیر است:
# In yek code vaghee nist! >>> b = entry2RCG(80) >>> print(b) {'c' : 8, 'r': 8, 'g': 8}
>>> 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.| +---+---+---+
>>> 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|...|...| +---+---+---+
نکتهی مهم این است که وظیفهی تشخیص حل سودوکو بر عهدهی findNextMove است. زمانی سودوکو کاملا حل شده است که در هیچ یک از اندیسهای متغیر __table هیچ لیستی وجود نداشته باشد. در این حالت متد مقدار [1000, 1000] را بر میگرداند که نشاندهندهی حل جدول سودوکو است.
نکتهی مهم دیگر اینست که در بسیاری از مواقع مسیری که الگوریتم برای حل سودوکو استفاده میکند به بنبست میخورد و دیگر امکان پیشروی ندارد. در این حالت باید از مسیر رفته عقبنشینی کنیم و مسیر جدیدی انتخاب کنیم. در این حالت findNextMove مقدار [-1,-1] را بر میگرداند که نشاندهندهی وجود بنبست و عدم امکان پیشروی است.
فراخوانی این متد بر مبنای الگوریتم برنامه میباشد ولی یک نمونه اجرای تستی این متد میتواند به صورت زیر باشد:
>>> 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 نمایش میدهیم. میتوانید صحت عملیات را از روی جدول تصدیق کنید.
وقتی کنترل از این دستور خارج شود به معنی حل شدن سودوکو است!
>>> 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* | +---------------------------+---------------------------+---------------------------+
علامت ستاره در بالای بعضی خانهها نشاندهندهی این است که آن خانه هنوز مقدار خود را نشناخته و اعداد لیست شده، اعداد «ممکن» آن خانه هستند.
نمونه کاربرد این متد را در زیر مشاهده میکنید:
>>> 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]]
میخواهیم ببینیم آیا برنامه خانههای مجاور خانهی شماره 0 در جدول سودوکو را درست محاسبه کرده است یا نه.
>>> 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 | | | +---+---+---+
کد زیر شمارهی خانههای قرار گرفته در سطر آخر جدول سودوکو را برمیگرداند.
>>> 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]
کد زیر شمارهی خانههای قرار گرفته در ستون اول جدول سودوکو را نشان میدهد.
>>> 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]
تکه کد زیر شمارهی خانههای واقع شده در دومین مربع جدول سودوکو را برمیگرداند.
>>> 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]
>>> 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| +---+---+---+
>>> 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.....
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..
# # 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("@@@@@@@@@@@@@")
کلیه حقوق برای دارندهی سایت محفوظ است.