"""
.. module:: matrix
:platform: Unix, Windows
:synopsis: traditional method of solving sudoku
.. moduleauthor:: Robert J. Hwang <RobertOfTaiwan@gmail.com>
"""
import copy, sys, itertools, time, os
#global var
rec = list()
records = 0
done = False
error = False
HasWritenPossible = False
PrintStep = True
[docs]def emptyMatrix():
"""init the matrix
return::
m: matrix map
n: the number's position, the first element save the numbers
p: the possible numbers in every position
"""
global rec, records
rec = list()
records = 0
m = list(x for x in range(10)) # By Position
n = list(x for x in range(10)) # By Number
p = list(x for x in range(10)) # Possible Number
for i in range(10):
m[i] = [0 for x in range(10)]
n[i] = [0 for x in range(10)]
p[i] = [0 for x in range(10)]
for j in range(1, 10):
p[i][j] = list(x for x in range(1, 10))
return m, n, p
[docs]def readDefine(file, m, n, p):
"""Reading the Matrix form a define file, the format must be as x,y,v
Save the file by the Unix text format
"""
f = open(file, "r")
i = 0
for line in f:
# print(line)
if len(line) > 0:
index = line.split(",")
pos = (int(index[0]), int(index[1]))
v = int(index[2])
setNumber(m, n, p, pos, v)
i += 1
return i
[docs]def setNumber(m, n, p, pos, v, logic="defined"):
"""Setting the position x, y to be number v"""
global records, rec, HasWritenPossible, error, PrintStep
# check first, if impossible, rasie the error flag
if not isPossible(m, p, pos, v):
error = True
return(0)
x, y = pos
m[0][0] += 1 # The total assigned number in the matrix
m[x][y] = v
m[x][0] += 1
m[0][y] += 1
n[v][0] += 1 # n[1..9][0] record every number(1..9)'s assigned numbers
#print( pos, v, n[v][0])
n[v][n[v][0]] = (x, y) # n[1..9][1..9] record every number(1..9)'s assigned position
#n[0][1..9] record the box 1-9's assigned numbers
b = WhichBox(pos); idx = (b[0] - 1) * 3 + b[1]
n[0][idx] += 1
p[x][y] = v
if logic == "defined":
pass
#print("set {0}, {1} to be {2} by {3}".format(x, y, v, logic))
else:
records += 1
rec.append((x, y, v, "s", logic))
if PrintStep:
print("Step#{0}: {1}, {2} to be set {3} by {4}".format(records, x, y, v, logic))
# same x
for i in range(1, 10):
if y != i and isinstance(p[x][i], list) and (v in p[x][i]):
if not HasWritenPossible:
p[x][i].remove(v)
else:
reduceNumber(m, n, p, (x, i), v, logic=logic)
# same y
for i in range(1, 10):
if x != i and isinstance(p[i][y], list) and (v in p[i][y]):
if not HasWritenPossible:
p[i][y].remove(v)
else:
reduceNumber(m, n, p, (i, y), v, logic=logic)
# same box
b = GetSameBoxOtherPos(m, p, (x, y))
for i, j in b:
if isinstance(p[i][j], list) and (v in p[i][j]):
if not HasWritenPossible:
p[i][j].remove(v)
else:
reduceNumber(m, n, p, (i, j), v, logic=logic)
return(1)
[docs]def reduceNumber(m, n, p, pos, v, logic="defined"):
"""Reduce the possible number of the position x, y from v
return: 0: Error, 1:reduce, 2:reduce and only one value left, so set the number"""
global records, rec, PrintStep
x, y = pos
if (not isinstance(p[x][y], list)) or (v not in p[x][y]):
print("error: {0} not in the the pos {2} which possible set: {1}".format(v, p[x][y], pos))
return 0
p[x][y].remove(v)
if logic == "defined":
pass
#print("set {0}, {1} to be {2} by {3}".format(x, y, v, logic))
else:
records += 1
rec.append((x, y, v, "r", logic))
if PrintStep:
print("Step#{0}: Reduce the position {1} from the value: {2} By {3}!".format(records, pos, v, logic))
# if the possible value is left to be one
if len(p[x][y]) == 1:
setNumber(m, n, p, pos, p[x][y][0], logic)
return 2
else:
return 1
[docs]def printMatrix(m):
"""print matrix(m)"""
for i in range(1, 10):
for j in range(1, 10):
print("{0:3}".format( m[j][i] ), end="")
print("")
[docs]def WhichBox(pos):
"""get a Box Postion(i, j) from a position (x, y)"""
return int((pos[0] - 1) / 3) + 1, int((pos[1] - 1) / 3) + 1
[docs]def GetEffectBox(p1, p2):
"""get Boxes Position(i, j) list from two positions which will effect these boxes"""
b1 = WhichBox(p1)
b2 = WhichBox(p2)
# the same x
if b1[0] == b2[0]:
y = [1,2,3]
y.remove(b1[1])
y.remove(b2[1])
return [(b1[0], y[0])]
# the same y
if b1[1] == b2[1]:
x = [1,2,3]
x.remove(b1[0])
x.remove(b2[0])
return [(x[0], b1[1])]
# x, y are all different
return [(b1[0], b2[1]), (b2[0], b1[1])]
[docs]def GetEffectBoxByOne(p1):
"""get Boxes Position(i, j) list by one positions which will effect these boxes"""
b1 = WhichBox(p1)
box = []
for i in range(1, 4):
for j in range(1, 4):
if (i == b1[0] or j == b1[1]) and (i, j) != b1:
box.append((i, j))
return box
[docs]def GetEffectBoxByOneDir(grp):
"""get Boxes Position(i, j) list by one group which will effect these boxes"""
b1 = WhichBox(grp[1][0]) # use the first possible position to get box id
box = []
for i in range(1, 4):
# the same x
if grp[0][1] == 0 and i != b1[1]:
box.append((b1[0], i))
# the same y
if grp[0][0] == 0 and i != b1[0]:
box.append((i, b1[1]))
return box
[docs]def GetEffectBoxByOnePosAndOneDir(p1, p2, grp):
"""get Boxes Position(i, j) list from one position and one group which will effect these boxes
but only get same x or same y box
grp: (x,0)|((0,y)"""
b1 = WhichBox(p1)
b2 = WhichBox(p2)
if b1 == b2:
return []
rtn = []
# the same x
if grp[0] != 0 and b1[0] == b2[0]:
y = [1,2,3]
y.remove(b1[1])
y.remove(b2[1])
rtn = [(b1[0], y[0])]
# the same y
elif grp[1] != 0 and b1[1] == b2[1]:
x = [1,2,3]
x.remove(b1[0])
x.remove(b2[0])
rtn = [(x[0], b1[1])]
# x, y are all different
elif b1[0] != b2[0] and b1[1] != b2[1]:
rtn = [(b1[0], b2[1])] if grp[1] != 0 else [(b2[0], b1[1])]
return rtn
[docs]def GetEffectBoxByTwoGrp(p1, p2, d1, d2):
"""get Boxes Position(i, j) list by two directed group which will effect these boxes
p1, p2: any position of those groups to make sure the whichbox
d1, d2: format like (x,0) or (0, y) to say the group's direction"""
b1 = WhichBox(p1)
b2 = WhichBox(p2)
rtn = []
#print(p1, p2, d1, d2, b1, b2)
if b1 == b2:
return rtn
# the same x
if d1[1] == 0 and d2[1] == 0 and b1[0] == b2[0]:
y = [1, 2, 3]
y.remove(b1[1])
y.remove(b2[1])
rtn = [(b1[0], y[0])]
# the same y
elif d1[0] == 0 and d2[0] == 0 and b1[1] == b2[1]:
x = [1, 2, 3]
x.remove(b1[0])
x.remove(b2[0])
rtn = [(x[0], b1[1])]
# d1 and d2 are different direction x, y are all different
elif d1[1] != d2[1] and d1[0] != d2[0] and b1[0] != b2[0] and b1[1] != b2[1]:
rtn = [(b1[0], b2[1])] if d1[0]!=0 else [(b2[0], b1[1])]
return rtn
[docs]def isInBox(m, p, b, number):
"""Check the number is filled in a box (i, j)"""
Pos = GetAllPosInBox(m, p, b)
for x, y in Pos:
if m[x][y] == number:
return True
return False
[docs]def GetAllPosInBox(m, p, b, method="a", num=0, diff=[]):
"""Getting a box's all position
method: a: all, s: all assigned, u: all un-assigned
num: 0(1-9), if method="u", if the num is 1-9, it will only take the positions that is possible be filled by the num
diff: the posithon in diff must be excluded"""
Pos = list()
checkdiff = len(diff) > 0
for i in range(1, 4):
for j in range(1, 4):
nX = (b[0] - 1)*3 + i
nY = (b[1] - 1)*3 + j
if (method == "s" and m[nX][nY] == 0) or (method == "u" and m[nX][nY] != 0):
continue
if num!=0 and method == "u" and (num not in p[nX][nY]):
continue
if checkdiff and (nX, nY) in diff:
continue
Pos.append((nX, nY))
return Pos
[docs]def GetSameBoxOtherPos(m, p, pos):
"""get the other postions in a box which there is a postion of x, y"""
b = GetAllPosInBox(m, p, WhichBox(pos))
b.remove(pos)
return b
[docs]def GetCanNotSeenInBox(m, b, p1, p2):
"""get the postions in a box(b) which can not be seen in position p1 and p2 which are in the same box
and those positions are not filled
p1, p2 must be in different x and y, p1, p2 sometime as the form (x,0)|(0,y)"""
Pos = list()
for i in range(1, 4):
for j in range(1, 4):
x = (b[0] - 1)*3 + i
y = (b[1] - 1)*3 + j
if x == p1[0] or x == p2[0] or y == p1[1] or y == p2[1] or m[x][y]!=0:
continue
Pos.append((x, y))
return Pos
[docs]def isDone(m):
"""Checking the Matrix is done or not
.. note: only Check the vertical amount is 9
"""
flag = True
for i in range(1, 10):
if m[0][i] != 9:
flag = False
break;
return flag
[docs]def isPossible(m, p, pos, v, groups=[]):
"""Check if the value v is possible at pos(x, y)"""
if not isPossibleByX(m, pos, v, groups):
return False
if not isPossibleByY(m, pos, v, groups):
return False
if not isPossibleByBox(m, p, pos, v):
return False
return True
[docs]def isPossibleByX(m, pos, v, groups=[]):
"""Check the same x if the value v is possible at pos(x, y)"""
# check the same x
for i in range(1, 10):
if pos[1] != i and m[pos[0]][i] == v:
return False
# check the group number
if len(groups) > 0:
b = WhichBox(pos)
for grp in groups:
# if in same box or the group is the same y, just ignore
if b == WhichBox(grp[1][0]) or grp[0][0] == 0:
continue
else:
if pos[0] == grp[0][0]:
return False
return True
[docs]def isPossibleByY(m, pos, v, groups=[]):
"""Check the same y if the value v is possible at pos(x, y)
if group number has passed, should check box group number"""
# check the same y
for i in range(1, 10):
if pos[0] != i and m[i][pos[1]] == v:
return False
# check the group number
if len(groups) > 0:
b = WhichBox(pos)
for grp in groups:
# if in same box or the group is the same x, just ignore
if b == WhichBox(grp[1][0]) or grp[0][1] == 0:
continue
else:
if pos[1] == grp[0][1]:
return False
return True
[docs]def isPossibleByBox(m, p, pos, v, groups=[]):
"""Check the same box if the value v is possible at pos(x, y)"""
# same box
b = GetSameBoxOtherPos(m, p, pos)
for i, j in b:
if m[i][j] == v:
return False
return True
[docs]def CheckObvious(m, n, p, amt=0):
"""Checking the every number in every two different position can descide
the number in other box which does not have the number yet"""
#print("Step #1: CheckObvious: {0}".format(amt))
for number in range(1, 10):
if n[number][0] <= 0 or n[number][0] >=9 :
continue
nums = n[number][0] + 1
for i in range(1, nums):
for j in range(1, nums):
if i == j:
break # same pos
effectBox = GetEffectBox(n[number][i], n[number][j])
for b in effectBox:
if not isInBox(m, p, b, number):
possiblePos = GetCanNotSeenInBox(m, b, n[number][i], n[number][j])
#print(number, n[number][i], n[number][j], possiblePos, b)
pos2 = copy.deepcopy(possiblePos)
for pos in pos2:
if not isPossibleByX(m, pos, number) or not isPossibleByY(m, pos, number):
possiblePos.remove(pos)
if len(possiblePos) == 1:
# if only one possible pos means it is the position of the number
# and it will use the same function to continue find another possible position for the number
amt += 1
setNumber(m, n, p, possiblePos[0], number, logic="Obvious for {0}".format(number))
# recall self: CheckObvious()
amt = CheckObvious(m, n, p, amt=amt)
return amt # Because it has launched another CheckObvious(), so it can be stopped here
return amt
[docs]def CheckObviousByOne(m, n, p, amt=0):
"""Checking every number with only one assigned numer or a group number to decide
the number in other box which does not have the number yet"""
#print("Step #1: CheckObviousByOne: {0}".format(amt))
for number in range(1, 10):
if n[number][0] <= 0 or n[number][0] >=9 :
continue
# Check every assigned position
for i in range(1, n[number][0] + 1):
effectBox = GetEffectBoxByOne(n[number][i])
for b in effectBox:
if not isInBox(m, p, b, number):
possiblePos = GetCanNotSeenInBox(m, b, n[number][i], (0, 0))
#print(number, n[number][i], n[number][j], possiblePos, b)
pos2 = copy.deepcopy(possiblePos)
for pos in pos2:
if not isPossibleByX(m, pos, number) or not isPossibleByY(m, pos, number):
possiblePos.remove(pos)
if len(possiblePos) == 1:
# if only one possible pos means it is the position of the number
# and it will use the same function to continue find another possible position for the number
amt += 1
setNumber(m, n, p, possiblePos[0], number, logic="ObviousByOne for {0}".format(number))
# recall self: CheckObvious()
amt = CheckObviousByOne(m, n, p, amt=amt)
return amt # Because it has launched another CheckObvious(), so it can be stopped here
return amt
[docs]def GetGroupInBox(m, n, p, number):
"""Get the number Groups which are formed natually in a box
because the remain possible positions can at the same line"""
groups = list()
amt = 0
for i in range(1, 4):
for j in range(1, 4):
Pos = GetAllPosInBox(m, p, (i, j), method="u", num=number)
possible = len(Pos)
if possible != 2 and possible != 3:
continue
g = GetIndirectNumberInBox(Pos)
if g != (0, 0):
amt += 1
groups.append((g, Pos))
sets = 0 # the amount of set Number
reduces = 0 # the amount of reduce Number
for grp in groups:
# the same x
if grp[0][1] == 0:
Pos = GetAllPosOfX(m, p, grp[0][0], diff=grp[1], method="u")
for p1 in Pos:
x, y = p1
if m[x][y] != 0 or number not in p[x][y]:
continue
rtn = reduceNumber(m, n, p, p1, number, logic="ByBoxGroup")
if rtn == 2:
sets += 1
elif rtn == 1:
reduces += 1
# the same y
else:
Pos = GetAllPosOfY(m, p, grp[0][1], diff=grp[1], method="u")
for p1 in Pos:
x, y = p1
if m[x][y]!=0 or number not in p[x][y]:
continue
rtn = reduceNumber(m, n, p, p1, number, logic="ByBoxGroup")
if rtn == 2:
sets += 1
elif rtn == 1:
reduces += 1
# if some group number effect something, recall self to check again
if reduces > 0 or sets > 0:
return GetGroupInBox(m, n, p, number)
else:
return groups
[docs]def GetAllPosOfX(m, p, idx, diff=[], method="a", num=0):
"""Get all other possition of line from x = idx than those in diff
method: a: all, s:has assigned, u:not assigned
num: if method is u and set the number to 1-9, will get all possible pos which are possible to be assigned the num"""
Pos = list()
k = 0
lGetOtherThan = len(diff) > 0
for i in range(1, 10):
if (method=="u" and m[idx][i]!=0) or (method=="s" and m[idx][i]==0):
continue
if lGetOtherThan and (idx, i) in diff:
continue
if num!=0 and method=="u" and num not in p[idx][i]:
continue
k += 1
Pos.append((idx, i))
return Pos
[docs]def GetAllPosOfY(m, p, idx, diff=[], method="a", num=0):
"""Get all other possition of line from y = idx than those in diff
method: a: all, s:has assigned, u:not assigned
num: if method is u and set the number to 1-9, will get all possible pos which are possible to be assigned the num"""
Pos = list()
k = 0
lGetOtherThan = len(diff) > 0
for i in range(1, 10):
if (method == "u" and m[i][idx] != 0) or (method == "s" and m[i][idx] == 0):
continue
if lGetOtherThan and (i, idx) in diff:
continue
if num != 0 and method == "u" and num not in p[i][idx]:
continue
k += 1
Pos.append((i, idx))
return Pos
[docs]def ReduceByBoxGroup(m, n, p):
"""Reduce Method #1: Reduce by the group number in a box"""
sets = 0 # the amount of set Number
reduces = 0 # the amount of reduce Number
for num in range(1, 10):
groups = GetGroupInBox(m, n, p, num)
for grp in groups:
# the same x
if grp[0][1] == 0:
Pos = GetAllPosOfX(m, p, grp[0][0], diff=grp[1], method="u")
for p1 in Pos:
if num not in p[p1[0]][p1[1]]:
continue
rtn = reduceNumber(m, n, p, p1, num, logic="ByBoxGroup")
if rtn == 2:
sets += 1
elif rtn == 1:
reduces += 1
# the same y
else:
Pos = GetAllPosOfY(m, p, grp[0][1], diff=grp[1], method="u")
for p1 in Pos:
if num not in p[p1[0]][p1[1]]:
continue
rtn = reduceNumber(m, n, p, p1, num, logic="ByBoxGroup")
if rtn == 2:
sets += 1
elif rtn == 1:
reduces += 1
return reduces, sets
[docs]def CheckInObvious(m, n, p, amt=0):
"""Checking the number in every two different position can decide
the number in other box which does not have the number yet
Parameters:
groups: [((x,0)|(0,y), [(x1,y1),(x2,y2)...]),...]
"""
#print("Step #2: CheckInObvious!")
for number in range(1, 10):
# if the number is done
if n[number][0] <= 0 or n[number][0] >=9 :
continue
# at first, add natual number groups into groups
groups = GetGroupInBox(m, n, p, number)
if len(groups) <= 0:
continue
# check every single group number
for grp in groups:
#print( grp )
effectBox = GetEffectBoxByOneDir(grp)
for b in effectBox:
if not isInBox(m, p, b, number):
possiblePos = GetCanNotSeenInBox(m, b, grp[0], (0, 0))
#print(number, n[number][i], n[number][j], possiblePos, b)
pos2 = copy.deepcopy(possiblePos)
for pos in pos2:
if not isPossibleByX(m, pos, number, groups=groups) or not isPossibleByY(m, pos, number, groups=groups):
possiblePos.remove(pos)
if len(possiblePos) == 1:
# if only one possible pos means it is the position of the number
# and it will use the same function to continue find another possible position for the number
amt += 1
setNumber(m, n, p, possiblePos[0], number, logic="InObviousByOne for {0}".format(number))
# check groups and have assigned position
for grp in groups:
nums = n[number][0] + 1
for j in range(1, nums):
effectBox = GetEffectBoxByOnePosAndOneDir(n[number][j], grp[1][0], grp[0])
for b in effectBox:
if not isInBox(m, p, b, number):
possiblePos = GetCanNotSeenInBox(m, b, grp[0], n[number][j])
pos2 = copy.deepcopy(possiblePos)
for pos in pos2:
if not isPossibleByX(m, pos, number, groups=groups) or not isPossibleByY(m, pos, number, groups=groups):
possiblePos.remove(pos)
if len(possiblePos) == 1:
# if only one possible pos means it is the position of the number
# and it will use the same function to continue find another possible position for the number
amt = amt + 1
# print(number, groups, n[number][j], b)
setNumber(m, n, p, possiblePos[0], number, logic="InObviousWithGroup for {0}".format(number))
# if there is only one group, just return
if len(groups) <= 1:
return amt
# check two groups:
for g1 in groups:
for g2 in groups:
effectBox = GetEffectBoxByTwoGrp(g1[1][0], g2[1][0], g1[0], g2[0])
for b in effectBox:
if not isInBox(m, p, b, number):
possiblePos = GetCanNotSeenInBox(m, b, g1[0], g2[0])
pos2 = copy.deepcopy(possiblePos)
for pos in pos2:
if not isPossibleByX(m, pos, number, groups=groups) or not isPossibleByY(m, pos, number, groups=groups):
possiblePos.remove(pos)
if len(possiblePos) == 1:
# if only one possible pos means it is the position of the number
# and it will use the same function to continue find another possible position for the number
amt = amt + 1
setNumber(m, n, p, possiblePos[0], number, logic="InObviousByTwoGroup for {0}".format(number))
return amt
[docs]def GetIndirectNumberInBox(possiblePos):
"""Get Indirect Number Group in a box by possible positions of a number
judge by if all ther possiblePos has a same direction, means that those have same x or y
if so, it will return (x, 0) or (0, y), otherwise will return (0, 0)
"""
flag = True
direction = "x"
for p1 in possiblePos:
for p2 in possiblePos:
if p1 == p2:
continue
if p1[0] != p2[0] and p1[1] != p2[1]:
flag = False
break
else:
# check direction
if p1[0] != p2[0]:
direction = "y"
if flag:
rtn = (p1[0], 0) if direction == "x" else (0, p1[1])
else:
rtn = (0, 0)
return rtn
[docs]def GetNotAssignedByX(m, x):
"""Get not yet be assigned positions and number by x"""
if m[x][0] >= 9: # check if that x line has been filled
return [], []
Pos = list()
Num = list(x for x in range(1, 10))
for i in range(1, 10):
if m[x][i] == 0:
Pos.append((x, i))
else:
Num.remove(m[x][i])
return Pos, Num
[docs]def CheckOnlyOnePossible(m, n, p, amt=0):
"""Checking the position which only has one possible value"""
#print("Step #3: CheckOnlyOnePossible: ".format(amt))
for i in range(1, 10):
for j in range(1, 10):
if isinstance(p[i][j],list) and len(p[i][j]) == 1:
amt += 1
setNumber(m, n, p, (i, j), p[i][j][0], logic="OnlyOnePossibleNumber!")
# When setNumber, the p LIST has been changed, so it should be stopped, so call self again
# to make sure that all position by x has been checked, then just return
return 1 # just get one then return, let other to process
#amt = CheckOnlyOnePossible(m, n, p, amt=amt)
#return amt
return amt
[docs]def CheckOnlyOnePossibleByPos(m, n, p, amt=0):
"""Checking the same positions is only one possible for the number"""
#print("Step #2: CheckOnlyOnePossibleByPos: {0}".format(amt))
for i in range(1, 10):
Pos, Num = GetNotAssignedByX(m, i)
if len(Pos) <= 0:
continue
#test every possible number which will only in one position?
for num in Num:
k = 0
idx = ()
for p1 in Pos:
x, y = p1
if num in p[x][y]:
k += 1
# if the count has over 1, it cannot be the only one, then test next number
if k >= 2:
break
else:
idx = p1
if k == 1:
amt += 1
setNumber(m, n, p, idx, num, logic="OnlyOnePositionByPos for {0}".format(num))
# When setNumber, the p LIST has been changed, so it should be stopped, so call self again
# to make sure that all position by x has been checked, then just return
# Just solve one, left to let other method to check
# amt = CheckOnlyOnePossibleByPos(m, n, p, amt=amt)
return amt
else:
if k > 2:
print("Here should not to be, it must be a bug!")
return amt
[docs]def fillLastNumberByX(m, n, p, i):
"""fill the x line's last number"""
num = [x for x in range(1, 10)]
for idx in range(1, 10):
if m[i][idx] == 0:
last = idx
else:
num.remove(m[i][idx])
if len(num) != 1:
print("Error: this is not the last number condition when x={0}".format(i))
#print(m, i, last, num)
#sys.exit(0)
return False
else:
setNumber(m, n, p, (i, last), num[0], logic="fillLastNumberbyX at LineX={0}".format(i))
return True
[docs]def fillLastNumberByY(m, n, p, i):
"""fill the y line's last number"""
num = [x for x in range(1, 10)]
for idx in range(1, 10):
if m[idx][i] == 0:
last = idx
else:
num.remove(m[idx][i])
if len(num) != 1:
print("Error: this is not the last number condition when y={0}".format(i))
#print(m, i, last, num)
#sys.exit(0)
return False
else:
setNumber(m, n, p, (last, i), num[0], logic="fillLastNumberbyY at LineY={0}".format(i))
return True
[docs]def fillLastNumberByBox(m, n, p, box):
"""fill the Box's last number"""
Pos = GetAllPosInBox(m, p, box)
num = [x for x in range(1, 10)]
for x, y in Pos:
if m[x][y] == 0:
lastX, lastY = x, y
else:
num.remove(m[x][y])
if len(num) != 1:
print("Error: this is not the last number condition when Box={0}".format(box))
#print(m, box, lastX, lastY, num)
#sys.exit(0)
return False
else:
setNumber(m, n, p, (lastX, lastY), num[0], logic="fillLastNumberbyBox at Box={0}".format(box))
return True
[docs]def CheckOnlyOnePossibleByNum(m, n, p, amt=0):
"""Check if there is only one number left in the same x, y or box"""
#print("Step #2: CheckOnlyOnePossibleByNum: {0}".format(amt))
# the same x
for i in range(1, 10):
if m[i][0] == 8 and fillLastNumberByX(m, n, p, i):
amt += 1
return CheckOnlyOnePossibleByNum(m, n, p, amt=amt)
# the same y
for i in range(1, 10):
if m[0][i] == 8 and fillLastNumberByY(m, n, p, i):
amt += 1
return CheckOnlyOnePossibleByNum(m, n, p, amt=amt)
# the same box
for i in range(1, 4):
for j in range(1, 4):
#n[0][1..9] record the box's assigned numbers
idx = (i - 1) * 3 + j
if n[0][idx] == 8 and fillLastNumberByBox(m, n, p, (i, j)):
amt += 1
return CheckOnlyOnePossibleByNum(m, n, p, amt=amt)
# if has assigned one, check again by self
if amt > 0:
return CheckOnlyOnePossibleByNum(m, n, p)
else:
return amt
[docs]def SortedUnAssignedPosByPossibles(m, p, possibles=0):
"""Get unassign position's possible number list, format is [(p1,[n1,n2,...]),(p2,[n1, n2,...]),...]
and Sorted By the possible numbers
possibles: 0 for all, >=2, mean get only the possible numbers for it
"""
rtn = []
CheckIt = possibles >= 2
for i in range(1, 10):
for j in range(1, 10):
if m[i][j] != 0:
continue
if CheckIt and len(p[i][j]) != possibles:
continue
rtn.append(((i, j), p[i][j]))
rtn = sorted(rtn, key=lambda pos: len(pos[1]))
return rtn
[docs]def TryError(file=None, m=[], n=[], p=[], depth=0):
"""Try Error method"""
global records, rec, HasWritenPossible, done, error, PrintStep
PrintStep = False
if file is not None:
records = 0 # record how many steps have been taken
rec = list() # record of step: (x, y, value, logic)
HasWritenPossible = False
done = False
error = False
if not os.path.isfile(file):
file = "data/" + file
try:
f = open(file, 'r')
except IOError:
print('Cannot open', file)
return False
else:
print(file, 'has', len(f.readlines()), ' defined!')
f.close()
m, n, p = emptyMatrix()
readDefine(file, m, n, p)
m1 = copy.deepcopy(m)
n1 = copy.deepcopy(n)
p1 = copy.deepcopy(p)
depth += 1
flag = False
possibles = SortedUnAssignedPosByPossibles(m1, p1)
for pos, pset in possibles:
k = len(pset)
if k <= 0:
return False
if k == 1:
setNumber(m1, n1, p1, pos, pset[0], logic="Only One!")
if isDone(m1):
done = True
print("done!")
printMatrix(m1)
return True
else:
return TryError(m=m1, n=n1, p=p1, depth=depth)
p2 = copy.deepcopy(p1)
n2 = copy.deepcopy(n1)
m2 = copy.deepcopy(m1)
i = 0
for num in pset:
i += 1
flag = False
#print("Depth#{2}-{3}: try {0} to be {1} of {4}".format(pos, num, depth, i, pset))
if isPossible(m1, p1, pos, num):
setNumber(m1, n1, p1, pos, num, logic="Try")
if isDone(m1):
done = True
print("done!")
printMatrix(m1)
return True
flag = TryError(m=m1, n=n1, p=p1, depth=depth)
if flag:
break
else:
# unset number
# unsetNumber(m1, n1, p1, pos, num, pset, logic="Try")
p1 = copy.deepcopy(p2)
n1 = copy.deepcopy(n2)
m1 = copy.deepcopy(m2)
continue
else:
#print("Impossible for {0} to be {1} in set of {2}".format(pos, num, pset))
continue
if flag:
if done:
return True
continue
else:
#print("Impossible for {0} in set of {1}".format(pos, pset))
return False
[docs]def GetChains(m, n, p, Pos, numbers=2):
"""Get numbers Chains from a Pos list
return: [([num1, num2,...], [pos1, pos2,...]),...]"""
# get the positions who's possible numbers is great than 1, and less or equal numbers
q = []
for x, y in Pos:
k = len(p[x][y])
if 1 < k <= numbers:
q.append((x, y))
# if qualified positions is less than numbers, just return
if len(q) < numbers:
return []
rtn = []
for c in itertools.combinations(q, numbers):
s = set()
for x, y in c:
s = s | set(p[x][y])
#print(x, y, p[x][y], s)
if len(s) == numbers:
rtn.append((list(s), list(c)))
return rtn
[docs]def ReduceByChain(m, n, p, numbers, pos, chainpos, logic="Reduced By Chain"):
"""Reduce numbers of positions of pos which other than positions of chainpos"""
reduces = 0
sets = 0
for x, y in pos:
if (x, y) in chainpos or m[x][y] != 0:
continue
for num in numbers:
if num in p[x][y]:
rtn = reduceNumber(m, n, p, (x, y), num, logic=logic)
if rtn == 2: # if set number, just return, let other method to deal with others
sets += 1
return reduces, sets
else:
reduces += 1
return reduces, sets
[docs]def ReduceByBoxChain(m, n, p):
"""Reduce By Box's chaing"""
reduces = 0
sets = 0
for i in range(1, 4):
for j in range(1, 4):
pos = GetAllPosInBox(m, p, (i,j), method="u")
k = len(pos)
for chainNums in range(2, 5): # just check 2, 3, 4 numbers' chain
if k < chainNums: # if the unsign positions are little than chains, not need to check
break
chains = GetChains(m, n, p, pos, numbers=chainNums)
for numbers, chainpos in chains:
amt, sets = ReduceByChain(m, n, p, numbers, pos, chainpos, logic="ByBoxChain:{0}".format(chainpos))
reduces += amt
if sets > 0:
reduces += 1
return reduces, sets
return reduces, sets
[docs]def ReduceByLineChain(m, n, p, direction="x"):
"""Reduce By Line chain
direction: x: the same x postions, y: the same y positions
"""
reduces = 0
sets = 0
for i in range(1, 10):
pos = GetAllPosOfX(m, p, i, method="u") if direction == "x" else GetAllPosOfY(m, p, i, method="u")
left = 9 - (m[i][0] if direction == "x" else m[0][i])
k = len(pos)
for chainNums in range(2, 5): # just check 2, 3, 4 numbers' chain
if k < chainNums or chainNums >= left: #if the unsign positions are little than chains, or great than the left positions, not need to check
break
chains = GetChains(m, n, p, pos, numbers=chainNums)
for numbers, chainpos in chains:
# print(numbers, chainpos, chainNums)
amt, sets = ReduceByChain(m, n, p, numbers, pos, chainpos, logic="ByLineChain:{0}".format(chainpos))
reduces = reduces + amt
if sets > 0:
reduces += 1
return reduces, sets
return reduces, sets
[docs]def ReduceByTwoPossible(m, n, p):
"""Reduce by a postion's two possible number
we assume the position set the first, then test the second number where the first number in of the same box, samy x, and same y
if we can get the number in the other position, we can make sure that in the other positions will not have the first number
because both of two possible number have been tested.
return: reduces, sets
"""
possibles = SortedUnAssignedPosByPossibles(m, p, possibles=2)
for pos, numbers in possibles:
x, y = pos
b = WhichBox(pos)
# check the first number as first, then check the second number as first
r0 = list()
r1 = list() # the result records of the two value
for i in range(1, 3):
first = p[x][y][0] if i == 1 else p[x][y][1]
second = p[x][y][1] if i == 1 else p[x][y][0]
for j in range(1, 4): # Check Box, x line, y line
# Get the effect positions which has the possible number in a Box
if j == 1: # box
effects = GetAllPosInBox(m, p, b, method='u', num=first, diff=[pos])
elif j == 2: # x line
effects = GetAllPosOfX(m, p, x, method='u', num=first, diff=[pos])
else: # y line
effects = GetAllPosOfY(m, p, y, method='u', num=first, diff=[pos])
if len(effects) <= 1:
continue
rtn, m1, r = Emulator(m, n, p, pos, second, targets=effects, checkval=first)
#print(pos, first, second, effects, rtn)
if rtn < 0: # error, so the value must be the first
setNumber(m, n, p, pos, first, logic="The Other Is Impossible By TwoPossible!")
return 0, 1
elif rtn > 1: # solve, so the value must be the second
setNumber(m, n, p, pos, second, logic="This value can solve all By TwoPossible!")
return 0, 1
elif rtn == 1: # one of effect positions can be set to be the first value
amt = ReduceByEmuResult(m, n, p, m1, effects, first)
if amt > 0:
return amt, 0
else: # rtn == 0, can't know anything, just continue
if i == 1:
r0 = r0 + r[records+1:]
else:
r1 = r1 + r[records+1:]
continue
if len(r0) > 0 and len(r1) > 0:
reduces, sets = CheckResultByTwoPossibleVal(m, n, p, r0, r1, logic="CheckResultByTwoPossibleVal of {0} at the Pos {1}".format(p[x][y], pos))
if reduces > 0 or sets > 0:
return reduces, sets
return 0, 0
[docs]def ReduceByTwoPositionInBox(m, n, p):
"""Reduce by two postions which in the same box or same line, and have a common
possible number which only be possible in these two different positions
we assume the position set the first, then test the second number where the first number in of the same box, samy x, and same y
if we can get the number in the other position, we can make sure that in the other positions will not have the first number
because both of two possible number have been tested.
return: reduces, sets
"""
for num in range(1, 10):
for i in range(1, 4):
for j in range(1, 4):
possible = GetAllPosInBox(m, p, (i, j), method='u', num=num)
if len(possible) != 2:
continue
r0 = list()
r1 = list()
for k in range(1, 3):
pos = possible[0] if k == 1 else possible[1]
theother = possible[1] if k == 1 else possible[0]
rtn, m1, r = Emulator(m, n, p, pos, num)
if rtn < 0: # error, so the value must be the other
setNumber(m, n, p, theother, num, logic="Impossible By TwoPosition!")
return 0, 1
elif rtn > 1: # solve, so the value must be the second
setNumber(m, n, p, pos, num, logic="This value can solve all By TwoPosition!")
return 0, 1
else: # rtn == 0, can't know anything, just continue
if k == 1:
r0 = r0 + r[records+1:]
else:
r1 = r1 + r[records+1:]
continue
if len(r0) > 0 and len(r1) > 0:
reduces, sets = CheckResultByTwoPossibleVal(m, n, p, r0, r1, logic="CheckResultByTwoPosition of {0}".format(possible))
if reduces > 0 or sets > 0:
return reduces, sets
return 0, 0
[docs]def ReduceByTwoPositionOfLine(m, n, p, direction="x"):
"""Reduce by two postions which in the same line, and have a common
possible number which only be possible in these two different positions
we assume the position set the first, then test the second number where the first number in of the same box, samy x, and same y
if we can get the number in the other position, we can make sure that in the other positions will not have the first number
because both of two possible number have been tested.
return: reduces, sets"""
for num in range(1, 10):
for i in range(1, 10):
if direction == "x":
possible = GetAllPosOfX(m, p, i, method='u', num=num)
else:
possible = GetAllPosOfY(m, p, i, method='u', num=num)
if len(possible) != 2:
continue
if WhichBox(possible[0]) == WhichBox(possible[1]):
continue
r0 = list()
r1 = list()
for k in range(1, 3):
pos = possible[0] if k == 1 else possible[1]
theother = possible[1] if k==1 else possible[0]
rtn, m1, r = Emulator(m, n, p, pos, num)
if rtn < 0: # error, so the value must be the other
setNumber(m, n, p, theother, num, logic="Impossible By TwoPosition Of a Line!")
return 0, 1
elif rtn > 1: # solve, so the value must be the second
setNumber(m, n, p, pos, num, logic="This value can solve all By TwoPosition Of a Line!")
return 0, 1
else: # rtn == 0, can't know anything, just continue
if k == 1:
r0 = r0 + r[records+1:]
else:
r1 = r1 + r[records+1:]
continue
if len(r0) > 0 and len(r1) > 0:
reduces, sets = CheckResultByTwoPossibleVal(m, n, p, r0, r1, logic="CheckResultByTwoPosition of {0}".format(possible))
if reduces > 0 or sets > 0:
return reduces, sets
return 0, 0
[docs]def CheckResultByTwoPossibleVal(m, n, p, r0, r1, logic="CheckResultByTwoPossible"):
"""Check two emulate result records from a number only have two possible position in a box, line;
or a postion only have two possible numbers,
if they have same record or not!
"""
reduces = 0; sets = 0
for x0, y0, v0, t0, logic0 in r0:
for x1, y1, v1, t1, login1 in r1:
if x1 == x0 and y1 == y0 and v1 == v0 and t1 == t0:
if t1 == "s":
if m[x1][y1] == 0:
sets += 1
setNumber(m, n, p, (x1, y1), v1, logic=logic)
else:
if isinstance(p[x1][y1], list) and v1 in p[x1][y1]:
reduces += 1
reduceNumber(m, n, p, (x1, y1), v1, logic=logic)
return reduces, sets
[docs]def ReduceByEmuResult(m, n, p, m1, possible, v):
"""Reduce v from some postions by emulate result m1"""
HasSet = False
for x, y in possible:
if m1[x][y] == v:
HasSet = True
break
if not HasSet:
return 0
possible.remove((x, y))
amt = 0
for x1, y1 in possible:
if m[x1][y1] == 0 and v in p[x1][y1]:
rtn = reduceNumber(m, n, p, (x1, y1), v, logic="ReduceByEmuResult!")
if rtn > 0:
amt += 1
return amt
[docs]def CheckVal(m, pos, v):
"""Check if one of the positions has been set the value"""
for x, y in pos:
if m[x][y] == v:
return True
return False
[docs]def Emulator(m, n, p, pos, v, targets=[], checkval=0):
"""Emulator
emulate the pos to be set v, then start to use some basic methods to try to solve
it will stop when and return::
1: one of the targets have been set the checkval
2: isDone
-1: error is True
0: all basic methods have been tested, and can't solve
and the result matrix
"""
global records, rec, HasWritenPossible, done, error, PrintStep
if len(targets) > 0:
CheckTarget = True
else:
CheckTarget = False
recSave = copy.deepcopy(rec)
recordsSave = records
m1 = copy.deepcopy(m)
n1 = copy.deepcopy(n)
p1 = copy.deepcopy(p)
PrintStep = False
setNumber(m1, n1, p1, pos, v, logic="Emulator Start!")
nTry = 0
nRtn = 0
while True:
# check
if isDone(m1):
nRtn = 2
break
if CheckTarget and CheckVal(m1, targets, checkval):
nRtn = 1
break
if error:
nRtn = -1
break
nTry += 1
nHasSet = m1[0][0]
# step#0, is there a line or a box which has only one position left?
if CheckOnlyOnePossibleByNum(m1, n1, p1) > 0:
continue
# step#1, Check Obvious by one position
if CheckObviousByOne(m1, n1, p1) > 0:
continue
# step#2
if CheckObvious(m1, n1, p1) > 0:
continue
# step#3, Reduce number by the Box Group number, and set it if it only one possible number left
if CheckInObvious(m1, n1, p1) > 0:
continue
# step #4, check Only One Possible By Position
if CheckOnlyOnePossibleByPos(m1, n1, p1) > 0:
continue
# step #5, check Only One Possible
if CheckOnlyOnePossible(m1, n1, p1) > 0:
continue
# step #6, reduce number by Box Group
reduces, sets = ReduceByBoxGroup(m1, n1, p1)
if reduces > 0 or sets > 0:
continue
# step #7, reduce number by Box Chain
reduces, sets = ReduceByBoxChain(m1, n1, p1)
if reduces > 0 or sets > 0:
continue
# step #8, reduce number by X Line Chain
reduces, sets = ReduceByLineChain(m1, n1, p1, direction="x")
if reduces > 0 or sets > 0:
continue
# step #9, reduce number by Y Line Chain
reduces, sets = ReduceByLineChain(m1, n1, p1, direction="y")
if reduces > 0 or sets > 0:
continue
# check
if isDone(m1):
nRtn = 2
break
if CheckTarget and CheckVal(m1, targets, checkval):
nRtn = 1
break
if error:
nRtn = -1
break
break
# restore
error = False
done = False
r = copy.deepcopy(rec)
rec = copy.deepcopy(recSave)
records = recordsSave
PrintStep = True
return nRtn, m1, r
[docs]def main(file, methods=0):
"""main program"""
global records, rec, HasWritenPossible, done, error
start = time.time()
limitMethods = False if methods == 0 else True
records = 0 # record how many steps have been taken
rec = list() # record of step: (x, y, value, logic)
HasWritenPossible = False
done = False
error = False
if not os.path.isfile(file):
file = "data/" + file
try:
f = open(file, 'r')
except IOError:
print('Cannot open', file)
return False
else:
print(file, 'has', len(f.readlines()), ' defined!')
f.close()
m, n, p = emptyMatrix()
readDefine(file, m, n, p)
nTry = 0
while not isDone(m):
nTry += 1
# step#0, is there a line or a box which has only one position left?
nHasSet0 = m[0][0]
amt = CheckOnlyOnePossibleByNum(m, n, p)
print("By Method#0, Try#{1}, we set {0} positions!".format(m[0][0] - nHasSet0, nTry))
if isDone(m):
break
else:
if amt > 0:
continue
if limitMethods and methods <= 0 and m[0][0] == nHasSet0:
break
# step#1, Check Obvious by one position
nHasSet1 = m[0][0]
amt = CheckObviousByOne(m, n, p)
print("By Method#1, Try#{1}, we set {0} positions!".format(m[0][0] - nHasSet1, nTry))
if isDone(m):
break
else:
if amt > 0:
continue
if limitMethods and methods <= 1 and m[0][0] == nHasSet0:
break
# step#2
nHasSet2 = m[0][0]
amt = CheckObvious(m, n, p)
print("By Method#2, Try#{1}, we set {0} positions!".format(m[0][0] - nHasSet2, nTry))
if isDone(m):
break
else:
if amt > 0:
continue
if limitMethods and methods <= 2 and m[0][0] == nHasSet0:
break
# step#3, Reduce number by the Box Group number, and set it if it only one possible number left
nHasSet3 = m[0][0]
CheckInObvious(m, n, p)
amt = m[0][0] - nHasSet3
print("By Method#3, Try#{1}, we set set {0} positions!".format(amt, nTry))
if isDone(m):
break
else:
if amt > 0:
continue
if limitMethods and methods <= 3 and m[0][0] == nHasSet0:
break
# step #4, check Only One Possible By Position
nHasSet4 = m[0][0]
amt = CheckOnlyOnePossibleByPos(m, n, p)
print("By Method#4, Try#{1}, we set {0} positions!".format(m[0][0] - nHasSet4, nTry))
if isDone(m):
break
else:
if amt > 0:
continue
if limitMethods and methods <= 4 and m[0][0] == nHasSet0:
break
# step #5, check Only One Possible
# assume here we have writen all possible number in unassgined position
if not HasWritenPossible:
HasWritenPossible = True
print("Write down every possible number in every un-assigned possition!")
nHasSet5 = m[0][0]
amt = CheckOnlyOnePossible(m, n, p)
print("By Method#5, Try#{1}, we set {0} positions!".format(m[0][0] - nHasSet5, nTry))
if isDone(m):
break
else:
if amt > 0:
continue
if limitMethods and methods <= 5 and m[0][0] == nHasSet0:
break
# step #6, reduce number by Box Group
nHasSet6 = m[0][0]
reduces, sets = ReduceByBoxGroup(m, n, p)
print("By Reduce#6, Try#{1}, we reduce {0} times and set {2} positions!".format(reduces, nTry, sets))
if isDone(m):
break
else:
if reduces > 0 or sets > 0:
continue
if limitMethods and methods <= 6 and m[0][0] == nHasSet0:
break
# step #7, reduce number by Box Chain
nHasSet7 = m[0][0]
reduces, sets = ReduceByBoxChain(m, n, p)
print("By Reduce#7, Try#{1}, we reduce {0} times and set {2} positions!".format(reduces, nTry, sets))
if isDone(m):
break
else:
if reduces > 0 or sets > 0:
continue
if limitMethods and methods <= 7 and m[0][0] == nHasSet0:
break
# step #8, reduce number by X Line Chain
nHasSet8 = m[0][0]
reduces, sets = ReduceByLineChain(m, n, p, direction="x")
print("By Reduce#8, Try#{1}, we reduce {0} times and set {2} positions!".format(reduces, nTry, sets))
if isDone(m):
break
else:
if reduces > 0 or sets > 0:
continue
if limitMethods and methods <= 8 and m[0][0] == nHasSet0:
break
# step #9, reduce number by Y Line Chain
nHasSet9 = m[0][0]
reduces, sets = ReduceByLineChain(m, n, p, direction="y")
print("By Reduce#9, Try#{1}, we reduce {0} times and set {2} positions!".format(reduces, nTry, sets))
if isDone(m):
break
else:
if reduces > 0 or sets > 0:
continue
if limitMethods and methods <= 9 and m[0][0] == nHasSet0:
break
# step#10, reduce number by having Two Possible number's postions
nHasSet10 = m[0][0]
reduces, sets = ReduceByTwoPossible(m, n, p)
print("By Reduce#10, Try#{1}, we reduce {0} times and set {2} positions!".format(reduces, nTry, sets))
if isDone(m):
break
else:
if reduces > 0 or sets > 0:
continue
if limitMethods and methods <= 10 and m[0][0] == nHasSet0:
break
# step#11, reduce number by only two possible positons in the same box which have the common possible value
nHasSet11 = m[0][0]
reduces, sets = ReduceByTwoPositionInBox(m, n, p)
print("By Reduce#11, Try#{1}, we reduce {0} times and set {2} positions!".format(reduces, nTry, sets))
if isDone(m):
break
else:
if reduces > 0 or sets > 0:
continue
if limitMethods and methods <= 11 and m[0][0] == nHasSet0:
break
# step#12, reduce number by only two possible positions in the same x line which have the common possible value
nHasSet12 = m[0][0]
reduces, sets = ReduceByTwoPositionOfLine(m, n, p, direction="x")
print("By Reduce#12, Try#{1}, we reduce {0} times and set {2} positions!".format(reduces, nTry, sets))
if isDone(m):
break
else:
if reduces > 0 or sets > 0:
continue
if limitMethods and methods <= 12 and m[0][0] == nHasSet0:
break
# step#13, reduce number by only two possible positons in the same x line which have the common possible value
nHasSet13 = m[0][0]
reduces, sets = ReduceByTwoPositionOfLine(m, n, p, direction="y")
print("By Reduce#13, Try#{1}, we reduce {0} times and set {2} positions!".format(reduces, nTry, sets))
if isDone(m):
break
else:
if reduces > 0 or sets > 0:
continue
if limitMethods and methods <= 13 and m[0][0] == nHasSet0:
break
# Can't solve position any more
if m[0][0] == nHasSet0:
break
else:
continue
if not isDone(m):
print("Still need to more effort for {0}".format(81 - m[0][0]))
printMatrix(m)
return m, n, p
print("Done!, it takes {0}!".format(time.time() - start))
printMatrix(m)
return m, n, p