-
Notifications
You must be signed in to change notification settings - Fork 0
/
futoshiki.py
97 lines (92 loc) · 2.26 KB
/
futoshiki.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
def futoshiki(matrix,lt,gt,size):
def next(r,c):
if c<(len(matrix[0])-1): return (r,c+1)
return (r+1,0)
def getPossibilities(row,col):
pos=set([i for i in range(1,size+1)])
for r in range(0,size):
if matrix[r][col] in pos: pos.remove(matrix[r][col])
for c in range(0,size):
if matrix[row][c] in pos: pos.remove(matrix[row][c])
if (row,col) in lt:
greats=lt[(row,col)]
for r,c in greats:
if (n:=matrix[r][c])!=0:
for rm in range(n,size+1):
if rm in pos: pos.remove(rm)
if (row,col) in gt:
lesses=gt[(row,col)]
for r,c in lesses:
if (n:=matrix[r][c])!=0:
for rm in range(0,n):
if rm in pos: pos.remove(rm)
return list(pos)
def solve(row,col):
if row>=len(matrix) or col>=len(matrix[0]): return True
if matrix[row][col]==0:
for n in getPossibilities(row,col):
matrix[row][col]=n
if solve(*next(row,col)): return True
matrix[row][col]=0
else:
if solve(*next(row,col)): return True
return False
solve(0,0)
_matrix=[
[0,0,0,0,0],
[4,0,0,0,2],
[0,0,4,0,0],
[0,0,0,0,4],
[0,0,0,0,0]
]
_lt={
(0,1):[(0,0)],
(0,3):[(0,2)],
(0,4):[(0,3)],
(3,3):[(3,4)],
(4,0):[(4,1)],
(4,1):[(4,2)]
}
_gt={
(0,0):[(0,1)],
(0,2):[(0,3)],
(0,3):[(0,4)],
(3,4):[(3,3)],
(4,1):[(4,0)],
(4,2):[(4,1)]
}
matrix=[
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,4,0,0,0]
]
lt={
(0,4):[(0,3)],
(1,0):[(0,0)],
(1,1):[(1,0),(2,1)],
(1,4):[(0,4)],
(2,0):[(1,0),(2,1)],
(2,1):[(2,2)],
(3,2):[(3,3)],
(3,3):[(3,4)],
(4,2):[(4,3)],
(4,3):[(3,3)],
(4,4):[(3,4)]
}
gt={
(0,3):[(0,4)],
(0,0):[(1,0)],
(0,4):[(1,4)],
(1,0):[(1,1),(2,0)],
(2,1):[(1,1),(2,0)],
(2,2):[(2,1)],
(3,3):[(3,2)],
(3,4):[(3,3)],
(4,3):[(4,2)],
(3,3):[(4,3)],
(3,4):[(4,4)]
}
futoshiki(matrix,lt,gt,5)
print(matrix)