-
Notifications
You must be signed in to change notification settings - Fork 0
/
chess.py
97 lines (81 loc) · 1.94 KB
/
chess.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
import copy
# knight (horse :D)
def threatens(a, b, cache = {}):
if (a, b) in cache:
return cache[(a,b)]
deltaX = abs(a[0] - b[0])
deltaY = abs(a[1] - b[1])
if (deltaX == 1 and deltaY == 2) or (deltaX == 2 and deltaY == 1):
cache[(a,b)] = True
else:
cache[(a,b)] = False
return cache[(a,b)]
def boardToStr(board):
s = ''
for i, r in enumerate(board):
for j, brd in enumerate(r):
s = s + str(brd)
return s
boards = {}
def maxPieces(board, pieceType, count = {1:0}):
pieces = []
for i, l in enumerate(board):
for j, b in enumerate(l):
if b:
pieces.append((i, j))
maxx = len(pieces)
count[1] += 1
print count[1], board, maxx
for i in range(n):
for j in range(n):
if not board[i][j]:
threatened = False
for p in pieces:
if threatens(p, (i, j)):
threatened = True
break
if not threatened:
board[i][j] = 1
bstr = boardToStr(board)
if bstr in boards:
board[i][j] = 0
return boards[bstr]
m = maxPieces(board, pieceType)
if m > maxx:
maxx = m
board[i][j] = 0
bstr = boardToStr(board)
boards[bstr] = maxx
return maxx
#backtracking solution
def maxPiecesBT(n, pieceType):
#in this one board is represented by a dictionary of pieces
brd = {}
maxx = 0
count = 1
boardStack = [copy.copy(brd)]
while boardStack:
brd = boardStack.pop()
for i in range(n):
for j in range(n):
# print i, j, brd
if not (i, j) in brd:
threatened = False
for p in brd:
if threatens(p, (i, j)):
threatened = True
if not threatened:
brd[(i, j)] = True
count +=1
if len(brd) > maxx: maxx = len(brd)
print count, brd, len(brd)
boardStack.append(copy.copy(brd))
# print boardStack, "&&&&&&&&&&&"
del brd[(i, j)]
return maxx
maxPiecesBT(3, 'knight')
n = 3
b = [[0]*n for x in range(n)]
# print maxPieces(b, 'knight')
# print threatens('', (0, 0), (1, 1)
# print boardToStr(b)