daily pastebin goal
59%
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. OK, I Understand
 
Top