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
starting_point = [choose_best_subsquare(new_state), choose_best_rows(new_state), choose_best_column(new_state)]
x, y, dummy = max(starting_point, key=lambda w: w[2])
new_state[y][x] = j
if sudoku_allowed((y, x, new_state)):
next_states.append(tuple(map(tuple, new_state)))
return next_states
y, x = -1, -1
for i in range(len(state)):
for j in range(len(state[i])):
if state[i][j] == 0:
y, x = i, j
break
possible_moves = [(y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)]
next_states = []
for move in possible_moves:
new_y, new_x = move
if 0 <= new_y < len(state) and 0 <= new_x < len(state[0]):
# make a copy of the state
new_state = [list(row) for row in state]
# swap tiles
new_state[y][x], new_state[new_y][new_x] = new_state[new_y][new_x], new_state[y][x]
# Convert state to a tuple of tuples
new_state_tuple = tuple(tuple(row) for row in new_state)
if puzzle_allowed(new_state_tuple):
next_states.append(new_state_tuple)
return next_states
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
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
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
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
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
# Helper Functions
def choose_best_rows(grid):
best_row = -1
x = -1
min_empty = len(grid)
for i in range(len(grid)):
empty_cells = grid[i].count(0)
if 0 < empty_cells < min_empty:
best_row = i
min_empty = empty_cells
x = grid[i].index(0)
return x, best_row, min_empty
def choose_best_column(grid):
best_col = -1
y = -1
min_empty = len(grid)
for i in range(len(grid)):
col = [row[i] for row in grid]
empty_cells = col.count(0)
if 0 < empty_cells < min_empty:
best_col = i
min_empty = empty_cells
y = col.index(0)
return best_col, y, min_empty
def choose_best_subsquare(grid):
x = -1
y = -1
best_val = len(grid)
for down in range(0, 9, 3):
for across in range(0, 9, 3):
subsquare = [grid[i][across: across + 3] for i in range(down, down + 3)]
zeros = sum([subsquare[i].count(0) for i in range(len(subsquare))])
if 0 < zeros < best_val:
best_val = zeros
for j in range(len(subsquare)):
if 0 in subsquare[j]:
x = across + subsquare[j].index(0)
y = down + j
break
return (x, y, best_val)