Python

No description

fork
loading
Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
'''
Sudoku Solver

Using sets to old all possibilities at each point in the puzzle.  The puzzle is solved
when all points contain "singleton" sets.

Note:  I am using the numerals 0 thru 8 for convenience instead of traditional 1 thru 9
'''

import numpy as np

def print_sudoku(A):
  # NOTE:  Only prints solved elements
  print()
  for I in range(3):
    for J in range(3):
      for i in range(3):
        for j in range(3):
          if len(A[I,J,i,j]) > 1:
            print('.', end = " ")
          else:
            p = next(iter(A[I,J,i,j]))
            print ('{}'.format(p), end = " ")
        print (end = "   ")
      print()
    print()
  
def reduce_subset(a):
  a = a.reshape(9,)
  for i in range(9):
    p = a[i]
    for j in range(i+1,9):
      q = a[j]
      if len(p) == 1:
        q = q - p  # set math
      if len(q) == 1:
        p = p - q
      a[j] = q
    a[i] = p
  return a.reshape(3,3)

def update_possibilities(A):
  #XY exclusion (boxes)
  for I in range(3):
    for J in range(3):
      A[I,J,:,:] = reduce_subset(A[I,J,:,:])
  #Xx exclusion (rows)
  for I in range(3):
    for i in range(3):
      A[I,:,i,:] = reduce_subset(A[I,:,i,:])
  #Yy exclusion (columns)
  for J in range(3):
    for j in range(3):
      A[:,J,:,j] = reduce_subset(A[:,J,:,j])

def find_guess(A):
  # Todo: Could optimize a lot here, I would think!!
  for I in range(3):
    for J in range(3):
        for i in range(3):
          for j in range(3):
            if len(A[I,J,i,j]) > 1:
              p = next(iter(A[I,J,i,j])) # cannot index into a set
              return (I,J,i,j,p)
  return None

def apply_guess(A, g):
  A[g[0], g[1], g[2], g[3]] = {g[4]}
  return A

def remove_guess(A, g):
  p = A[g[0], g[1], g[2], g[3]]
  A[g[0], g[1], g[2], g[3]] = p - {g[4]}
  return A

def final_answer(A):
  tests = [len(p)==1 for p in A.reshape(81,)]
  return np.all(tests)

def broken_answer(A):
  tests = [len(p)==0 for p in A.reshape(81,)]
  return np.any(tests)

def solve(V):
  '''
  solve will only return on Success or Failure.  
  If it is still searching, it will recursively call itself again.
  '''
  A = V[-1]
  update_possibilities(A)
  
  if final_answer(A) or broken_answer(A):
    return
  else:  
    # Make a guess, add a new trial to the vector, and solve (recursive)
    guess = find_guess(A)
    B = A.copy()      # need to make a "deep" copy 
    apply_guess(B, guess)
    V.append(B)
    solve(V) 
  
  # If solve(V) returns, we either have success or a dead-end
  if final_answer(B):
    return
  else:
    # if prior solve reached a dead-end, "pop" it off the stack
    # try this step again, but eliminate the prior guess from the possibilities
    V.pop()
    remove_guess(A, guess)
    solve(V)

# Setup
# difficult to create an np.array of lists.    
A = np.empty(81, dtype=object)
for i in range(81): A[i] = {n for n in range(9)} # set comprehension
A = A.reshape(3,3,3,3)

# Seed the puzzle (should build a reader)
A[0,0,0,0] = {0}
A[0,0,0,1] = {1}
A[0,0,0,2] = {2}
A[1,0,0,2] = {3}
A[2,0,0,2] = {8}
A[1,0,1,1] = {5}

# print starting state
print_sudoku(A)

# Start a Vector of partial answers
update_possibilities(A)
V = [A]

# Loop until final answer or broken
solve(V)

# we're done! 
if len(V) > 0:
  A = V[-1]
  print ('Solved in {} steps'.format(len(V)))
  print_sudoku(V[-1])
else:
  print ('The puzzle is not solvable -- invalid starting state')