@@ -0,0 +1,867 @@
+# -*- coding: utf-8 -*-%0Aimport draw%0Aimport grid%0Aimport util%0A%0Adef iddfs(g, start, goal):%0A    for i in range(40):%0A        path = iddfs_rec(g, start, goal, %5Bstart%5D, i)%0A        if path != None:%0A            return path%0A    return None%0A%0Adef iddfs_rec(g, pos, goal, path, max_depth):%0A    if len(path) %3E max_depth:%0A        return None%0A    if pos == goal:%0A        return path%0A%0A    for n in g.neighbours(*pos):%0A        if n in path:%0A            continue # don't follow loops%0A        p = iddfs_rec(g, n, goal, path + %5Bn%5D, max_depth)%0A        if p != None:%0A            return p%0A    return None%0A%0Aif __name__ == '__main__':%0A    g, start, goal = util.generate_problem(16, 16, 0.2)%0A    print('Start:', start, 'goal:', goal)%0A    path = iddfs(g, start, goal)%0A    print('Found length vs heuristic:', len(path), grid.dist(start, goal))%0A%0A    draw.draw_path(draw.draw_grid(g), path).show()%0A

Add Iterative Deepening Depth-First Search