Newer
Older
def maze_successor(state):
next_states = [(state[0] + 1, state[1]),
(state[0], state[1] + 1),
(state[0] - 1, state[1]),
(state[0], state[1] - 1)]
next_states = [s for s in next_states if maze_allowed(s)]
return next_states
new_state = list(map(list, state)) # Convert state to a list of lists
y, x = -1, -1
for i, s in enumerate(state):
if 0 in s:
(y, x) = (i, s.index(0))
break
next_states = []
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
new_state[y][x] = j
if sudoku_allowed((y, x, new_state)):
next_states.append(tuple(map(tuple, new_state)))
return next_states
def maze_allowed(state):
maze = [[' ', 'W', ' ', ' ', 'G'],
[' ', 'W', ' ', 'W', ' '],
[' ', 'W', ' ', ' ', ' '],
[' ', ' ', 'W', 'W', ' '],
[' ', ' ', ' ', ' ', ' ']]
if state[0] >= len(maze[0]) or state[0] < 0:
return False
if state[1] >= len(maze) or state[1] < 0:
return False
return maze[state[0]][state[1]] == ' ' or maze[state[0]][state[1]] == 'G'
def sudoku_allowed(state):
(y, x, grid) = state
"""I'm making the state a triple on this one"""
# (y, x, z): x,y is the coordinate and z is the value in the square
# check if still inside the box
if y < 0 or y >= len(grid[0]):
return False
if x < 0 or x >= len(grid):
return False
# inspect columns and rows
if ([row[x] for row in grid].count(grid[y][x]) > 1) or (grid[y].count(grid[y][x]) > 1):
return False
# inspect minor square in teh sudoku
inner_x = ((x - (x % 3)), (x - (x % 3) + 3))
inner_y = (y - (y % 3))
inner_square = grid[inner_y][inner_x[0]:inner_x[1]] + grid[inner_y + 1][inner_x[0]:inner_x[1]] + \
grid[inner_y + 2][inner_x[0]:inner_x[1]]
if inner_square.count(grid[y][x]) > 1:
return False
return True
def puzzle_successor(state):
return []
def queens_successor(state):
new_state = list(map(list, state)) # Convert state to a list of lists
y = -1
for i in range(len(new_state)):
if sum(new_state[i]) == 0:
y = i
break
next_states = []
for j in range(len(new_state[0])):
new_state[y] = [False] * len(new_state[y])
new_state[y][j] = True
if queens_allowed((y, j, new_state)):
next_states.append(tuple(map(tuple, new_state)))
return next_states
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
def queens_allowed(state):
"""in this case the state is also y, x, grid"""
y, x, grid = state
# check if still inside the box
if y < 0 or y >= len(grid):
return False
if x < 0 or x >= len(grid[0]):
return False
# inspect columns and rows for queens
if (sum([row[x] for row in grid]) > 1) or (sum(grid[y]) > 1):
return False
# inspect diagonal
for i in range(1, len(grid)):
# positive diagonal
if x - i >= 0 and y - i >= 0 and grid[y - i][x - i]:
return False
if x + i < len(grid[0]) and y + i < len(grid) and grid[y + i][x + i]:
return False
# negative diagonal
if x - i >= 0 and y + i < len(grid) and grid[y + i][x - i]:
return False
if x + i < len(grid[0]) and y - i >= 0 and grid[y - i][x + i]:
return False
return True