• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Mar 23rd, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/env python3
2. #
3. # RNG based brute force sudoku solver
4. # Kinda slow sometimes but gets the job done
5. # Usage: sdk.py [SUDOKU_STRING]
6. # SUDOKU_STRING is a 81 character string of all rows in grid.
7. # Empty squares are marked as 0
8. # If grid is solved, will test if solution is legit
9.
10. import random
11. import sys
12.
13. TO_TEST = """
14. 080020560000100007000000000050090408007800003030010050204000800060085000000200100
15. 004970235530000000000000098060025000400000001000640050670000000000000019192054800
16. 100070030830600000002900608600004907090000050307500004203009100000002043040080009
17. 200010050305042000018009002032100800001020300009003260100700980000260507060080003
18. """
19.
20. def test(solution):
21.     d = [int(i) for i in solution]
22.     if sum(d) == 45 * 9:
23.         for i in range(0, 9):
24.             if sum([int(c) for c in d[i * 9 : i * 9 + 9]]) != 45:
25.                 print("KO")
26.                 return
27.         print("OK")
28.         return
29.     print("KO")
30.
31. def solve(input):
32.     def valid(i, val):
33.         def get(i):
34.             return dict(
35.                 x=i // 9,
36.                 y=i % 9,
37.                 z=(i // 3) % 3 + (i // 27) * 3
38.             )
39.         tmp = [(get(j), c) for j, c in enumerate(data)]
40.         cur = get(i)
41.         for c in 'xyz':
42.             if str(val) in [d[1] for d in tmp if d[0][c] == cur[c]]:
43.                 return False
44.         return True
45.
46.     data = list(input)
47.     metrics = dict(asrt=0, flush=0)
48.
49.     print("> INPUT")
50.     for i in range(0, 9):
51.         print(data[i * 9 : i * 9 + 9])
52.
53.     uc = []
54.     while '0' in data:
55.         for i, c in enumerate(data):
56.             if c == "0":
57.                 pos = [val for val in range(1, 10) if valid(i, val)]
58.                 if len(pos) == 1:
59.                     data[i] = str(pos[0])
60.                     uc.append(i)
61.                     break
62.                 if len(pos) == 0:
63.                     for u in uc:
64.                         data[u] = "0"
65.                     metrics['flush'] += 1
66.                     uc = []
67.                     break
68.         else:
69.             factor = 2
70.             while factor:
71.                 for i, c in enumerate(data):
72.                     if c == "0":
73.                         pos = [val for val in range(1, 10) if valid(i, val)]
74.                         if len(pos) == factor:
75.                             data[i] = str(random.choice(pos))
76.                             uc.append(i)
77.                             metrics['asrt'] += 1
78.                             factor = 0
79.                             break
80.                 else:
81.                     factor += 1
82.     print("> SOLUTION")
83.     for i in range(0, 9):
84.         print(data[i * 9 : i * 9 + 9])
85.     print("> METRICS")
86.     print(metrics)
87.     print("> STR: %s" % "".join(data))
88.
89. if __name__ == "__main__":
90.     if len(sys.argv) == 2:
91.         if len(sys.argv[1]) == 81:
92.             if "0" in sys.argv[1]:
93.                 solve(sys.argv[1])
94.             else:
95.                 test(sys.argv[1])
96.             sys.exit(0)
97.     print("INVALID INPUT")
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top