Merge pull request #2767 from LubosKolouch/master

Solutions task 1 Perl Python LK - refactor

1 files changed, 145 insertions, 0 deletions

diff --git a/challenge-086/lubos-kolouch/python/ch-2.py b/challenge-086/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..f827eec8d6
--- /dev/null
+++ b/challenge-086/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,145 @@
+#!env python
+"""
+#===============================================================================
+#
+#         FILE: ch-2.py
+#
+#        USAGE: ./ch-2.py
+#
+#  DESCRIPTION: Perl Weekly Challenge 086
+#  				Task 2
+#  				Sudoku Puzzle
+#
+#  				Uses backtrack algorithm
+#
+#       AUTHOR: Lubos Kolouch
+#      CREATED: 11/15/2020 01:27:06 PM
+#===============================================================================
+"""
+
+import re
+from copy import deepcopy
+
+
+def load_puzzle(puzzle_input):
+    """ load the puzzle from the input """
+
+    puzzle = []
+    for row in puzzle_input:
+        row = re.sub("_", "0", row)
+
+        puzzle.append(list(map(int, row.split(' '))))
+
+    return puzzle
+
+
+def get_valid_options(puzzle, row, col):
+    """ eliminate numbers 1-9 that are already taken """
+
+    valid_options = {}
+
+    for i in range(10):
+        valid_options[i] = 1
+
+    # eliminate already taken numbers
+    for i in range(9):
+        try:
+            del valid_options[puzzle[row][i]]
+        except:
+            pass
+
+    for i in range(9):
+        try:
+            del valid_options[puzzle[i][col]]
+        except:
+            pass
+
+    if not valid_options:
+        return
+
+    # eliminate quadrant
+
+    for row_shift in range(3):
+        for col_shift in range(3):
+            row_pos = row // 3 * 3 + row_shift
+            col_pos = col // 3 * 3 + col_shift
+
+            try:
+                del valid_options[puzzle[row_pos][col_pos]]
+            except:
+                pass
+
+    return valid_options
+
+
+def solve_position(puzzle_input):
+    # backtrack recursively to find the solution
+
+    next_puzzle = deepcopy(puzzle_input)
+
+    for row, row_data in enumerate(next_puzzle):
+        for col, item in enumerate(row_data):
+
+            if item != 0:
+                continue
+
+            valid_options = get_valid_options(puzzle=next_puzzle, row=row, col=col)
+
+            if not valid_options:
+                # nothing left to try, check if the solution is complete
+
+                for test_row in next_puzzle:
+                    for test_item in test_row:
+                        if item == 0:
+                            return
+
+                return next_puzzle
+
+            for next_key in valid_options:
+                next_puzzle[row][col] = next_key
+
+                next_iteration = solve_position(deepcopy(next_puzzle))
+
+                if next_iteration:
+                    return next_iteration
+
+    # great, we could fill all empty positions!
+    return next_puzzle
+
+
+def print_puzzle(puzzle):
+    """ print the puzzle """
+
+    for row in puzzle:
+        print(' '.join(list(map(str, row))))
+    print()
+
+
+def solve_sudoku(puzzle):
+    """ let's solve the puzzle! """
+
+    puzzle = load_puzzle(puzzle)
+    print_puzzle(puzzle)
+    solution = solve_position(puzzle)
+    print_puzzle(solution)
+    return solution
+
+
+assert solve_sudoku(['_ _ _ 2 6 _ 7 _ 1',
+                     '6 8 _ _ 7 _ _ 9 _',
+                     '1 9 _ _ _ 4 5 _ _',
+                     '8 2 _ 1 _ _ _ 4 _',
+                     '_ _ 4 6 _ 2 9 _ _',
+                     '_ 5 _ _ _ 3 _ 2 8',
+                     '_ _ 9 3 _ _ _ 7 4',
+                     '_ 4 _ _ 5 _ _ 3 6',
+                     '7 _ 3 _ 1 8 _ _ _']) == [
+                        [4, 3, 5, 2, 6, 9, 7, 8, 1],
+                        [6, 8, 2, 5, 7, 1, 4, 9, 3],
+                        [1, 9, 7, 8, 3, 4, 5, 6, 2],
+                        [8, 2, 6, 1, 9, 5, 3, 4, 7],
+                        [3, 7, 4, 6, 8, 2, 9, 1, 5],
+                        [9, 5, 1, 7, 4, 3, 6, 2, 8],
+                        [5, 1, 9, 3, 2, 6, 8, 7, 4],
+                        [2, 4, 8, 9, 5, 7, 1, 3, 6],
+                        [7, 6, 3, 4, 1, 8, 2, 5, 9], ]