Chapterبەش 4 · Lectureوانە 4.3

Solving a Maze with DFS and BFSچارەسەرکردنی لابیرینت بە DFS و BFS

Lab 2 step by step: the maze as a grid, the Point class, the directions list, the move check, DFS that returns the explored cells or the real path, eight directions, safe user input without eval(), and BFS for a guaranteed shortest path.

تاقیگەی 2 هەنگاو بە هەنگاو: وەک خانەبەندی، Point، لیستی ئاڕاستەکان، پشکنینی جووڵە، DFS کە خانە پشکنراوەکان یان ڕێگە ڕاستەقینەکە دەگەڕێنێتەوە، هەشت ئاڕاستە، پارێزراو بەبێ ⁦eval()⁩ و BFS بۆ بە گەرەنتییەوە.

21 min read19 خولەک خوێندنەوە · 14 stepsهەنگاو

What you will learnچی فێر دەبیت

Represent a maze as a list of strings and cells as (row, column) points.
Generate neighbours with a directions list and check that a move is valid.
Tell the explored list from the path, and rebuild the path from parent links.
Read user input safely: int(), range checks, try/except, no eval().
Explain why DFS paths are not always shortest and use BFS to get a shortest path.

وەک لیستێک لە و خانەکان وەک خاڵی (ڕیز، ستوون) نیشان بدەیت.
دراوسێکان بە لیستی ئاڕاستەکان دروست بکەیت و بپشکنیت کە جووڵەیەک دروستە.
لە ڕێگە جیا بکەیتەوە و ڕێگەکە لە پەیوەندیی باوکەکانەوە دروست بکەیتەوە.
بە پارێزراوی بخوێنیتەوە: ⁦int()⁩، پشکنینی مەودا، ⁦try/except⁩، بێ ⁦eval()⁩.
ڕوونی بکەیتەوە بۆچی ڕێگاکانی DFS هەمیشە کورتترین نین و BFS بەکار بهێنیت بۆ بەدەستهێنانی .

The Lab 2 mazeلابیرینتەکەی تاقیگەی 2

Lab 2 uses depth-first and breadth-first search (from the previous lesson) on a real problem: finding a way through a maze. The maze is a search problem like the ones in Search problems: the open cells are the states, and the moves are the actions.

تاقیگەی 2 و (لە وانەی پێشوو) لەسەر کێشەیەکی ڕاستەقینە بەکار دەهێنێت: دۆزینەوەی ڕێگە بە ناو . وەک ئەوانەی کێشەکانی گەڕان: خانە کراوەکان و جووڵەکان .

In Python the maze is a of , one string per row. A dot . is an open cell and # is a wall:

لە لە ، بۆ هەر ڕیزێک یەک . خاڵ . خانەیەکی کراوەیە و # دیوارە:

The maze as a list of stringsلابیرینتەکە وەک لیستێک لە زنجیرەنووسەکانPYTHON

maze = [
    "...##....",  # row 0
    ".#...####",  # row 1
    ".#.#....#",  # row 2
    "##.##.##.",  # row 3
    "....#....",  # row 4
]

The maze with row and column numbers, as in the lab's maze.txt. لەگەڵ ژمارەی ڕیز و ستوون، وەک فایلی ⁦maze.txt⁩ی تاقیگە.CêIT

A cell is written (x, y) = (row, column): x goes down, y goes across. maze[x][y] reads one cell, for example maze[0][3] is #. Every Lab 2 program starts at (0, 0) and ends at (4, 8). A list of rows is a ; PHP stores tables the same way (see rows and columns in PHP).

خانەیەک بەم شێوەیە دەنووسرێت: ⁦(x, y)⁩ = (ڕیز، ستوون): x بەرەو خوار دەڕوات و y بەرەو لا. maze[x][y] یەک خانە دەخوێنێتەوە، بۆ نموونە maze[0][3] بریتییە لە #. هەموو تاقیگەی 2 لە ⁦(0, 0)⁩ دەست پێدەکەن و لە ⁦(4, 8)⁩ کۆتایی دێن. لیستێک لە ڕیزەکان ؛ PHP خشتەکان بە هەمان شێوە هەڵدەگرێت (بڕوانە ڕیز و ستوون لە PHP).

In the code each cell is a Point object with x and y. The lab gives Point a __repr__ method so that printing shows (x, y) instead of the object's memory address (see Classes: the Point of the maze labs).

لە کۆدەکەدا هەر خانەیەک Pointـە کە x و yی هەیە. تاقیگەکە __repr__ دەدات بە Point بۆ ئەوەی چاپکردن (x, y) پیشان بدات نەک ناونیشانی لە (بڕوانە کلاسەکان: Pointی تاقیگەکانی لابیرینت).

Moving: the directions listجووڵان: لیستی ئاڕاستەکان

A move is a pair [dx, dy]: how many rows and how many columns we step. Each item of the directions list is one such pair:

هەر جووڵەیەک جووتێکی [dx, dy]ە: چەند ڕیز و چەند ستوون هەنگاو دەنێین. هەر دانەیەکی لیستی directions یەکێکە لەم جووتانە:

UP [-1, 0]: from the current cell to the cell directly above it (one row less, the column stays).
LEFT [0, -1]: to the cell directly to the left (the row stays, one column less).
DOWN [1, 0]: to the cell directly below (one row more).
RIGHT [0, 1]: to the cell directly to the right (one column more).

سەرەوە [-1, 0]: لە خانەی ئێستاوە بۆ ئەو خانەیەی ڕاستەوخۆ لە سەرەوەیەتی (ڕیزێک کەمتر، ستوونەکە وەک خۆی).
چەپ [0, -1]: بۆ ئەو خانەیەی ڕاستەوخۆ لە لای چەپیەتی (ڕیزەکە وەک خۆی، ستوونێک کەمتر).
خوارەوە [1, 0]: بۆ ئەو خانەیەی ڕاستەوخۆ لە خوارەوەیەتی (ڕیزێک زیاتر).
ڕاست [0, 1]: بۆ ئەو خانەیەی ڕاستەوخۆ لە لای ڕاستیەتی (ستوونێک زیاتر).

New cell = current cell + [dx, dy]. The corners are the diagonal moves used later.خانەی نوێ = خانەی ئێستا + ⁦[dx, dy]⁩. گۆشەکان ئەو جووڵە لارانەن کە دواتر بەکار دێن.CêIT

The code computes the new cell with x = dx + current.x and y = dy + current.y. current.x is the current row and dx is the vertical change (+1, 0 or −1), so x is the new row. In the same way y is the new column. The lab comments work this out by hand for the point (2, 3), and one version adds a small test loop (“this [1, 3] is only a test”) that prints the four new cells of a test point. Here is that test for (2, 3):

کۆدەکە خانە نوێیەکە بە x = dx + current.x و y = dy + current.y دەدۆزێتەوە. current.x ڕیزی ئێستایە و dx گۆڕانی بەرەو سەرەوە یان خوارەوەیە (⁦+1⁩، 0 یان ⁦−1⁩)، بۆیە x ڕیزە نوێیەکەیە. بە هەمان شێوە y ستوونە نوێیەکەیە. لێدوانەکانی تاقیگە ئەمە بە دەست بۆ خاڵی ⁦(2, 3)⁩ ئەنجام دەدەن و لە وەشانێکدا بۆ تاقیکردنەوە هەیە («ئەم ⁦[1, 3]⁩ـیە تەنها تاقیکردنەوەیە») کە چوار خانە نوێیەکەی خاڵێکی تاقیکردنەوە چاپ دەکات. ئەمە هەمان تاقیکردنەوەیە بۆ ⁦(2, 3)⁩:

Testing the directionsتاقیکردنەوەی ئاڕاستەکانmaze_directions.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

directions = [
    [-1, 0],  # UP:    one row less, same column
    [0, -1],  # LEFT:  same row, one column less
    [1, 0],   # DOWN:  one row more, same column
    [0, 1],   # RIGHT: same row, one column more
]

x, y = 2, 3  # only a test point: row 2, column 3
for dx, dy in directions:
    print([dx, dy], "->", (x + dx, y + dy))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 8

A test point, not part of the search.

خاڵێکی تاقیکردنەوە، بەشێک نییە لە گەڕانەکە.

Lineدێڕی 9-10

for dx, dy in directions unpacks each pair into two variables.

for dx, dy in directions هەر جووتێک دەکاتەوە بە دوو .

The order of the list matters for DFS. The natural order to think of is RIGHT, DOWN, LEFT, UP (“the row stays, add one to the column” and so on); the lab marks it “by our intuition, not a general formula”. Because DFS uses a stack, the last direction added is tried first, so the lab reverses the list to UP, LEFT, DOWN, RIGHT (it swaps item 0 with item 3 and item 1 with item 2). Then RIGHT is pushed last and is tried first.

ڕیزبەندیی لیستەکە بۆ DFS گرنگە. ڕیزبەندییە سروشتییەکە بۆ بیرکردنەوە ڕاست، خوارەوە، چەپ، سەرەوەیە («ڕیزەکە وەک خۆی بێت، ستوونەکە یەکێکی بخە سەر» و بەم شێوەیە)؛ تاقیگەکە دەڵێت ئەمە «بە هەستی خۆمانە، نەک یاسایەکی گشتی». چونکە DFS بەکار دەهێنێت، دوایین ئاڕاستە کە زیاد دەکرێت یەکەم جار تاقی دەکرێتەوە، بۆیە تاقیگەکە لیستەکە پێچەوانە دەکاتەوە بۆ سەرەوە، چەپ، خوارەوە، ڕاست (دانەی 0 لەگەڵ دانەی 3 و دانەی 1 لەگەڵ دانەی 2 ئاڵوگۆڕ دەکات): «ئەمەی سەرەوە دەبێت پێچەوانە بکرێتەوە، چونکە بەکار دەهێنین». بەم شێوەیە ڕاست لە کۆتاییدا دادەنرێت و یەکەم جار تاقی دەکرێتەوە.

Which moves are allowed?کام جووڵانە ڕێگەپێدراون؟

Before a new cell (x, y) goes into the frontier, one long condition checks four things: x and y are not negative, they do not go past the maze, the cell is not a wall, and it was not seen before.

پێش ئەوەی خانەیەکی نوێی ⁦(x, y)⁩ بچێتە ناو ، مەرجێکی درێژ چوار شت دەپشکنێت: x و y سالب نین، لە دەرناچن، خانەکە دیوار نییە و پێشتر نەبینراوە.

The move conditionمەرجی جووڵانPYTHON

if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] != wall and not seen[x][y]:
    frontier.append(Point(x, y))

0 <= x — not above the first row.
x < len(maze) — inside the maze's height (5 rows: 0 to 4). Together: we do not leave the maze vertically.
0 <= y < len(maze[0]) — the same for the columns (9 columns: 0 to 8).
maze[x][y] != wall — not a wall. not seen[x][y] — not visited before.

0 <= x — لە سەرووی ڕیزی یەکەمەوە نییە.
x < len(maze) — لە ناو بەرزیی (⁦5⁩ ڕیز: 0 تا ⁦4⁩). پێکەوە: بە ئاڕاستەی سەرەوە و خوارەوە لە دەرناچین.
0 <= y < len(maze[0]) — هەمان شت بۆ ستوونەکان (⁦9⁩ ستوون: 0 تا ⁦8⁩).
maze[x][y] != wall — دیوار نییە. not seen[x][y] — پێشتر سەردان نەکراوە.

Correctionڕاستکردنەوە

One lab comment says the condition checks that x and y are “positive integers”. The right word is not negative: 0 is allowed, and row 0 is the first row. The order of the tests also matters: Python checks them from left to right and stops at the first False, so maze[x][y] is only read when x and y are already known to be inside the maze.

لێدوانێکی تاقیگە دەڵێت مەرجەکە دەپشکنێت کە x و y «ژمارەی تەواوی ئەرێنین». وشە ڕاستەکە سالب نینە: 0 ڕێگەپێدراوە و ڕیزی 0 یەکەم ڕیزە. ڕیزبەندیی پشکنینەکانیش گرنگە: لە چەپەوە بۆ ڕاست دەیانپشکنێت و لە یەکەم Falseدا دەوەستێت، بۆیە maze[x][y] تەنها کاتێک دەخوێنرێتەوە کە پێشتر زانراوە x و y لە ناو .

seen is a history grid: a list of lists of False, one value per cell, set to True when a cell is visited. The lab first types it out by hand (five rows of nine False), then shows two shorter ways: “the quick way” with a , and “the quicker way” with a , seen = [[False for c in row] for row in maze]. Both ways are shown step by step in Grids: lists inside a list.

seen خانەبەندیی مێژوویە: لیستێک لە لیستی False، بۆ هەر خانەیەک یەک نرخ، کە کاتێک سەردانی خانەیەک دەکرێت دەبێت بە True. تاقیگەکە سەرەتا بە دەست دەینووسێت (پێنج ڕیز لە نۆ False)، پاشان دوو ڕێگای کورتتر پیشان دەدات: «ڕێگای خێرا» بە و «ڕێگای خێراتر» بە ، seen = [[False for c in row] for row in maze]. هەردوو ڕێگاکە هەنگاو بە هەنگاو لە خانەبەندی: لیست لە ناو لیستدا پیشان دراون.

DFS that returns the explored cellsDFS کە خانە پشکنراوەکان دەگەڕێنێتەوە

Now the whole search. solve() keeps a frontier list, an explored list and the seen grid. In the loop it pops the last point (a stack, so DFS). If the point is the end, it stops. Otherwise it marks the point as visited in both the explored list and the seen grid, and pushes every allowed neighbour.

ئێستا هەموو گەڕانەکە. solve() ، و خانەبەندیی seen هەڵدەگرێت. لە دوایین خاڵ دەردەهێنێت (، کەواتە DFS). ئەگەر خاڵەکە کۆتایی بێت، دەوەستێت. دەنا خاڵەکە لە هەردوو و خانەبەندیی seen وەک سەردانکراو نیشانە دەکات و هەموو دراوسێیەکی ڕێگەپێدراو دەخاتە ناو .

Maze DFS: every cell it exploredDFSی لابیرینت: هەموو ئەو خانانەی پشکنیونیmaze_explored.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f"({self.x}, {self.y})"


def solve(maze, wall, start, end):
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]  # up, left, down, right
    frontier = [start]
    explored = []
    seen = [[False for _ in row] for row in maze]  # a "history" grid

    while frontier:
        current = frontier.pop()  # stack -> depth-first search

        if current.x == end.x and current.y == end.y:
            return explored  # every cell we explored (not the path!)

        explored.append(current)
        seen[current.x][current.y] = True

        for dx, dy in directions:
            x, y = current.x + dx, current.y + dy
            if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] != wall and not seen[x][y]:
                frontier.append(Point(x, y))

    return explored


maze = [
    "...##....",  # 0
    ".#...####",  # 1
    ".#.#....#",  # 2
    "##.##.##.",  # 3
    "....#....",  # 4
]

explored = solve(maze, "#", Point(0, 0), Point(4, 8))
print("Explored:", explored)
print(len(explored), "cells explored before reaching the end")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 11

Up, left, down, right — already reversed for the stack.

سەرەوە، چەپ، خوارەوە، ڕاست — پێشتر بۆ پێچەوانە کراوەتەوە.

Lineدێڕی 14

The seen grid is made inside solve(), so the function does not depend on a global variable.

خانەبەندیی seen لە ناو solve()دا دروست دەکرێت، بۆیە پشت بە نابەستێت.

Lineدێڕی 17

pop() takes the last point: depth-first.

pop() دوایین خاڵ وەردەگرێت: قووڵایی.

Lineدێڕی 19-20

At the end we return the explored list — every cell visited, not the route.

لە کۆتاییدا دەگەڕێنینەوە — هەموو خانە سەردانکراوەکان، نەک ڕێگەکە.

This list is not the pathئەم لیستە ڕێگەکە نییە

The lab's version prints this list as Path: [...], and another solution as Path found: [...]. But it is not a path: it contains the dead end (2, 6), (2, 7) — cells the search tried and left — and it does not contain the end cell (4, 8). (A December version appends the end cell before returning, which gives 15 cells; still not a path.) We renamed the output “Explored” and the variable explored (the lab file spells it exploerd). One commented copy also uses a seen grid that is created after solve(), as a global; it works only because the grid exists before the call — create it inside the function instead.

وەشانەکەی تاقیگە ئەم لیستە وەک Path: [...] چاپ دەکات و چارەسەرێکی تر وەک Path found: [...]. بەڵام ئەمە نییە: ڕێگە داخراوەکەی ⁦(2, 6)⁩، ⁦(2, 7)⁩ تێدایە — ئەو خانانەی گەڕانەکە تاقیی کردنەوە و جێی هێشتن — و خانەی کۆتایی ⁦(4, 8)⁩ی تێدا نییە. (وەشانێکی مانگی دیسەمبەر پێش گەڕاندنەوە خانەی کۆتایی زیاد دەکات، کە دەبێت بە ⁦15⁩ خانە؛ هێشتا ڕێگە نییە.) ئێمە ناوی دەرئەنجامەکەمان کرد بە «Explored» و ناوی بە explored (فایلەکەی تاقیگە بە exploerd دەینووسێت). وێنەیەکی تری لێدواندار خانەبەندیی seen دوای solve() وەک دروست دەکات؛ تەنها لەبەر ئەوە کار دەکات کە خانەبەندییەکە پێش بانگکردنەکە هەیە — باشترە لە ناو دروستی بکەیت.

To make it breadth-first, the header comment of the lab says: insert 0 into pop(). (It also says to change the directions back to their natural order; that only changes which equal-length route is found first — BFS is correct either way.) Another solution says the same in its comment: “for BFS, just change it to .pop(0)”; that file also has a stray - line that stops it with a SyntaxError until it is removed.

بۆ ئەوەی ببێت بە پانایی، لێدوانی سەرەتای تاقیگەکە دەڵێت: 0 بخەرە ناو pop(). (هەروەها دەڵێت ئاڕاستەکان بگەڕێنەوە بۆ ڕیزبەندییە سروشتییەکەیان؛ ئەمە تەنها ئەوە دەگۆڕێت کە کام ڕێگەی هاوتەریب یەکەم جار دەدۆزرێتەوە — BFS بە هەردوو شێوە دروستە.) چارەسەرێکی تر هەمان شت لە لێدوانەکەیدا دەڵێت: «بۆ BFS تەنها بیکە بە .pop(0)»؛ ئەو فایلە دێڕێکی زیادەی -ی تێدایە کە بە SyntaxError ڕایدەگرێت تا لادەبرێت.

Quick checkپشکنینی خێراThe explored list contains (2, 6) and (2, 7). Are they on the way from (0, 0) to (4, 8)? ⁦(2, 6)⁩ و ⁦(2, 7)⁩ی تێدایە. ئایا ئەمانە لەسەر ڕێگەی ⁦(0, 0)⁩ بۆ ⁦(4, 8)⁩ن؟Yes, every explored cell is on the pathبەڵێ، هەموو خانەیەکی پشکنراو لەسەر ڕێگەکەیەNo, they are a dead end that DFS tried and leftنەخێر، ڕێگەیەکی داخراون کە DFS تاقیی کردنەوە و جێی هێشتن

Returning only the pathگەڕاندنەوەی تەنها ڕێگەکە

The lab comments name two types of explored path: (1) all the cells that were explored; (2) only the direct path, with nothing extra and no winding. To get the second one, every point must remember where it came from:

لێدوانەکانی تاقیگە ناوی دوو جۆری ڕێگەی پشکنراو دەهێنن: ⁦(1)⁩ هەموو ئەو خانانەی پشکنران؛ ⁦(2)⁩ تەنها ڕێگەی ڕاستەوڕاست، بێ زیادە و پێچوپەنا. بۆ بەدەستهێنانی جۆری دووەم، هەموو خاڵێک دەبێت لە بیری بێت لە کوێوە هاتووە:

From explored cells to a pathلە خانە پشکنراوەکانەوە بۆ ڕێگە

Give Point a third parameter parent=None.
سێیەم بدە بە Point: parent=None.
Push each neighbour as Point(x, y, current): its parent is the current point.
هەر دراوسێیەک بە شێوەی Point(x, y, current) بخەرە ناو : خاڵی ئێستایە.
When the end is reached, follow the parent links back to the start and collect the points.
کاتێک کۆتایی دەگات، پەیوەندییەکانی parent تا سەرەتا بگرە و خاڵەکان کۆ بکەرەوە.
Return path[::-1]: the list reversed, from start to end.
path[::-1] بگەڕێنەوە: لیستەکە پێچەوانەکراو، لە سەرەتاوە بۆ کۆتایی.

Maze DFS that returns only the pathDFSی لابیرینت کە تەنها ڕێگەکە دەگەڕێنێتەوەmaze_path.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

class Point:
    def __init__(self, x, y, parent=None):
        self.x = x
        self.y = y
        self.parent = parent  # the point we came from

    def __repr__(self):
        return f"({self.x}, {self.y})"


def solve(maze, wall, start, end):
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]  # up, left, down, right
    frontier = [start]
    seen = [[False for _ in row] for row in maze]

    while frontier:
        current = frontier.pop()

        if current.x == end.x and current.y == end.y:
            path = []
            while current:                # follow the parent links back to the start
                path.append(current)
                current = current.parent
            return path[::-1]             # reverse: from start to end

        seen[current.x][current.y] = True

        for dx, dy in directions:
            x, y = current.x + dx, current.y + dy
            if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] != wall and not seen[x][y]:
                frontier.append(Point(x, y, current))  # remember the parent

    return []  # no path


maze = [
    "...##....",  # 0
    ".#...####",  # 1
    ".#.#....#",  # 2
    "##.##.##.",  # 3
    "....#....",  # 4
]

path = solve(maze, "#", Point(0, 0), Point(4, 8))
print("Path found:", path)
print(len(path), "cells,", len(path) - 1, "moves")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 2-5

Each point tracks its parent node.

هەر خاڵێک لە بیر دەگرێت.

Lineدێڕی 19-24

Walk back along the parents, then reverse.

بە درێژایی باوکەکاندا بگەڕێوە دواوە، پاشان پێچەوانەی بکەرەوە.

Lineدێڕی 31

The new point remembers current as its parent.

خاڵە نوێیەکە current وەک لە بیر دەگرێت.

Lineدێڕی 33

An empty list means there is no path.

لیستێکی بەتاڵ واتە هیچ ڕێگەیەک نییە.

The path DFS found (green) and the dead end it explored on the way (blue).ئەو ڕێگەیەی DFS دۆزییەوە (سەوز) و ئەو ڕێگە داخراوەی بە ڕێگاوە پشکنی (شین).CêIT

Here the DFS path has 12 moves, and a breadth-first search also needs 12, so this route happens to be one of the shortest. DFS does not guarantee that. In the next screens the same maze with diagonal moves makes DFS take a longer route. (A practice copy of this program, study.py, returns the explored list instead of [] when there is no path.)

لێرەدا ڕێگەکەی ⁦DFS 12⁩ جووڵەیە و ⁦12⁩ جووڵەی پێویستە، بۆیە ئەم ڕێگەیە بە ڕێکەوت یەکێکە لە کورتترینەکان. DFS گەرەنتیی ئەمە ناکات. لە شاشەکانی داهاتوودا هەمان لەگەڵ جووڵەی لار وا دەکات DFS ڕێگەیەکی درێژتر بگرێتەبەر. (وێنەیەکی ڕاهێنانی ئەم ، study.py، کاتێک ڕێگە نییە لەبری [] دەگەڕێنێتەوە.)

Eight directions and drawing the pathهەشت ئاڕاستە و کێشانی ڕێگەکە

The next lab version adds the four diagonal moves [-1, -1], [-1, 1], [1, -1] and [1, 1] and draws the result: it copies the maze into a list of lists (strings cannot be changed, lists can), writes $ on every path cell and prints the maze again. trace_path() follows the .parent links and reverses the list. The lab's solve() also returns the explored list together with the end point and uses a hand-typed global seen grid; the version below returns only the end point and builds seen itself.

وەشانی دواتری تاقیگە چوار جووڵەی لار زیاد دەکات [-1, -1]، [-1, 1]، [1, -1] و [1, 1] و ئەنجامەکە دەکێشێت: دەگوازێتەوە بۆ لیستێک لە لیست ( ناگۆڕدرێن، لیستەکان دەگۆڕدرێن)، $ لەسەر هەموو خانەیەکی ڕێگەکە دەنووسێت و دووبارە چاپ دەکاتەوە. trace_path() پەیوەندییەکانی .parent دەگرێت و لیستەکە پێچەوانە دەکاتەوە. solve()ی تاقیگە هەروەها لەگەڵ خانەی کۆتایی دەگەڕێنێتەوە و خانەبەندییەکی seenی گشتی بەکار دەهێنێت کە بە دەست نووسراوە؛ وەشانەکەی خوارەوە تەنها خانەی کۆتایی دەگەڕێنێتەوە و seen خۆی دروست دەکات.

DFS with eight directions, drawing the path with $DFS بە هەشت ئاڕاستە، کێشانی ڕێگەکە بە $maze_8dir.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.parent = None

    def __repr__(self):
        return f"({self.x}, {self.y})"


def print_maze(maze):
    for row in maze:
        print("".join(row))


def solve(maze, wall, start, end):
    directions = [
        [-1, 0], [0, -1], [1, 0], [0, 1],     # up, left, down, right
        [-1, -1], [-1, 1], [1, -1], [1, 1],   # the four diagonals
    ]
    frontier = [start]
    seen = [[False for _ in row] for row in maze]

    while frontier:
        current = frontier.pop()  # DFS
        if current.x == end.x and current.y == end.y:
            return current
        seen[current.x][current.y] = True
        for dx, dy in directions:
            x, y = current.x + dx, current.y + dy
            if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] != wall and not seen[x][y]:
                neighbor = Point(x, y)
                neighbor.parent = current
                frontier.append(neighbor)
    return None


def trace_path(end):
    path = []
    current = end
    while current:
        path.append(current)
        current = current.parent
    return path[::-1]  # from the start to the end


maze = [
    "...##....",
    ".#...####",
    ".#.#....#",
    "##.##.##.",
    "....#....",
]

print_maze(maze)
print()
end_point = solve(maze, "#", Point(0, 0), Point(4, 8))
if end_point:
    path = trace_path(end_point)
    grid = [list(row) for row in maze]  # strings cannot change, lists can
    for p in path:
        grid[p.x][p.y] = "$"
    print("The path DFS found:", len(path) - 1, "moves")
    print_maze(grid)
else:
    print("No path found.")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 11-13

print_maze() prints each row as one string. (The lab builds the string with a loop and +=; "".join(row) does the same in one step.)

print_maze() هەر ڕیزێک وەک یەک چاپ دەکات. (تاقیگەکە بە و += دروست دەکات؛ "".join(row) هەمان کار بە یەک هەنگاو دەکات.)

Lineدێڕی 18-19

Four straight moves, then the four diagonals.

چوار جووڵەی ڕاست، پاشان چوار لارەکە.

Lineدێڕی 32-34

The parent is stored before the point goes into the frontier.

پێش ئەوەی خاڵەکە بچێتە ناو هەڵدەگیرێت.

Lineدێڕی 60-62

A string cannot be changed, so each row becomes a list; then $ marks the path.

ناگۆڕدرێت، بۆیە هەر ڕیزێک دەبێت بە لیست؛ پاشان $ ڕێگەکە نیشانە دەکات.

“Optimal path”? No.«ڕێگەی باشترین»؟ نەخێر.

The lab prints this result under the title “Maze with Optimal Path”. It is not optimal. Read the $ signs: the route goes (0,0) (0,1) (1,2) (1,3) (2,4) (3,5) (4,6) (4,7) (3,8) (4,8) — it climbs up to (3,8) and comes back down, 9 moves where 8 are enough. DFS returns the first route it finds, not the best one. Call it “the path DFS found”, and use breadth-first search when you need the shortest route.

تاقیگەکە ئەم ئەنجامە لە ژێر ناونیشانی « لەگەڵ ڕێگەی باشترین» چاپ دەکات. باشترین نییە. سەیری نیشانەکانی $ بکە: ڕێگەکە دەڕوات ⁦(0,0) (0,1) (1,2) (1,3) (2,4) (3,5) (4,6) (4,7)⁩ ⁦(3,8)⁩ ⁦(4,8)⁩ — بەرەو سەرەوە بۆ ⁦(3,8)⁩ دەچێت و دیسان دادەبەزێتەوە، 9 جووڵە لە کاتێکدا 8 بەسە. DFS یەکەم ڕێگە دەگەڕێنێتەوە کە دەیدۆزێتەوە، نەک باشترینیان. پێی بڵێ «ئەو ڕێگەیەی DFS دۆزییەوە» و کاتێک دەوێت بەکار بهێنە.

Cutting cornersبڕینی گۆشەکان

With diagonal moves the walker can cut the corner of a wall. Its very first diagonal step, (0,1) → (1,2), passes the corner of the wall at (1,1); later steps such as (1,3) → (2,4) do the same. It could even slip between two walls that touch only at a corner. A real person could not walk through a corner like that. Decide whether your problem allows it; if not, accept a diagonal move only when both cells beside it are open.

لەگەڵ جووڵەی لار، ڕێبوار دەتوانێت گۆشەی دیوارێک ببڕێت. یەکەم هەنگاوی لاری، ⁦(0,1)⁩ ← ⁦(1,2)⁩، بە گۆشەی دیوارەکەی ⁦(1,1)⁩دا تێدەپەڕێت؛ هەنگاوەکانی دواتر وەک ⁦(1,3)⁩ ← ⁦(2,4)⁩ هەمان شت دەکەن. تەنانەت دەتوانێت لە نێوان دوو دیواردا خۆی تێپەڕێنێت کە تەنها لە گۆشەیەکدا بەیەک دەگەن. مرۆڤێکی ڕاستەقینە ناتوانێت بەم شێوەیە بە ناو گۆشەیەکدا بڕوات. بڕیار بدە ئایا کێشەکەت ڕێگە بەمە دەدات؛ ئەگەر نا، جووڵەی لار تەنها کاتێک وەربگرە کە هەردوو خانەی تەنیشتی کراوە بن.

Correctionڕاستکردنەوە

A printed copy of the 4-direction version in the lab material is titled “Greedy Best First Search (filling the optimal path)”. It has no and no : it is plain DFS. That copy also ends with print("No path found.”) — a curly closing quote — which Python rejects with a SyntaxError. Always use straight quotes in code.

وێنەیەکی چاپکراوی وەشانە 4 ئاڕاستەییەکە لە کەرەستەی تاقیگەدا ناونیشانی «⁦Greedy Best First Search (filling the optimal path)⁩»ی هەیە. هیچ و هیچ تێدا نییە: DFSی سادەیە. ئەو وێنەیە بە print("No path found.”) کۆتایی دێت — کۆتەیشنێکی داخستنی خوار — کە بە SyntaxError ڕەتی دەکاتەوە. هەمیشە لە کۆددا کۆتەیشنی ڕاست بەکار بهێنە.

Quick checkپشکنینی خێراWhy does the program turn each row into a list before writing $?بۆچی پێش نووسینی $ هەر ڕیزێک دەکات بە لیست؟Because lists print fasterچونکە لیستەکان خێراتر چاپ دەبنBecause Python strings cannot be changed in placeچونکە زنجیرەنووسەکانی Python لە شوێنی خۆیاندا ناگۆڕدرێنBecause DFS needs listsچونکە DFS پێویستی بە لیستە

Letting the user choose start and endڕێگەدان بە بەکارهێنەر سەرەتا و کۆتایی هەڵبژێرێت

The last Lab 2 program (“DFS & BFS — Maze Optimized”) asks the user for the start and the end. It keeps the eight directions, but stores the parents in a parent = {start: None} instead of in each point. backtrack() then follows parent.get(current) until it reaches None and returns the reversed list. “Optimized” here means with input checks, not a faster algorithm.

دوایین تاقیگەی 2 («⁦DFS & BFS — Maze Optimized⁩») سەرەتا و کۆتایی لە دەپرسێت. هەشت ئاڕاستەکە دەهێڵێتەوە، بەڵام باوکەکان لە هەڵدەگرێت parent = {start: None} لەبری هەر خاڵێک. پاشان backtrack() parent.get(current) دەگرێت تا دەگاتە None و لیستە پێچەوانەکراوەکە دەگەڕێنێتەوە. «Optimized» لێرەدا واتە لەگەڵ پشکنینی ، نەک خێراتر.

The lab's main loop reads two numbers for the start and two for the end, converts them with eval(), and prints “Invalid Input. Try again.” when a cell is beyond the maze, is a wall, or when start = end. Otherwise it solves the maze, prints the path and stops (break). A printed variant puts the same check inside solve() (“the new check”, printing “Start or End is/are invalid.”) and shows both a one-time input version and the while True version.

سەرەکیی تاقیگە دوو ژمارە بۆ سەرەتا و دوو ژمارە بۆ کۆتایی دەخوێنێتەوە، بە eval() دەیانگۆڕێت و کاتێک خانەیەک لە دەرەوەی بێت، دیوار بێت، یان سەرەتا = کۆتایی بێت «⁦Invalid Input. Try again⁩.» چاپ دەکات. دەنا چارەسەر دەکات، ڕێگەکە چاپ دەکات و دەوەستێت (break). وەشانێکی چاپکراو هەمان پشکنین دەخاتە ناو solve() («پشکنینە تازەکە»، کە «⁦Start or End is/are invalid⁩.» چاپ دەکات) و هەم وەشانی یەکجاری و هەم وەشانی while True پیشان دەدات.

Runs of the lab's input program (DFS)جێبەجێکردنەکانی تاقیگە ⁦(DFS)⁩
Typed start / endسەرەتا / کۆتایی نووسراو	Result of the lab programئەنجامی تاقیگە
`0 0` / `4 8`	Path found: (0,0) (0,1) (1,2) (1,3) (2,4) (3,5) (4,6) (4,7) (3,8) (4,8) — 9 moves⁦Path found: (0,0) (0,1) (1,2) (1,3) (2,4) (3,5) (4,6) (4,7) (3,8) (4,8) — 9⁩ جووڵە
`0 3` / `4 8`	Invalid Input (0, 3 is a wall)⁦Invalid Input (0, 3⁩ دیوارە)
`0 0` / `0 0`	Invalid Input (start = end)⁦Invalid Input⁩ (سەرەتا = کۆتایی)
`0 0` / `4 0`	Path found: (0,0) (0,1) (1,2) (1,3) (2,2) (3,2) (4,3) (4,2) (4,1) (4,0) — 9 moves; the shortest has 6⁦Path found: (0,0) (0,1) (1,2) (1,3) (2,2) (3,2) (4,3) (4,2) (4,1) (4,0) — 9⁩ جووڵە؛ کورتترینیان 6ە
`0 0` / `0 8`	A 17-cell path (16 moves) that wanders through row 2 and back; a shortest 8-direction route has 8 movesڕێگەیەکی ⁦17⁩ خانەیی (⁦16⁩ جووڵە) کە بە ڕیزی 2دا دەسووڕێتەوە و دەگەڕێتەوە؛ 8 ئاڕاستەیی 8 جووڵەیە

Quick checkپشکنینی خێراWhy are the lab's paths for (0, 0) → (4, 0) and (0, 0) → (0, 8) so long?بۆچی ڕێگاکانی تاقیگە بۆ ⁦(0, 0)⁩ ← ⁦(4, 0)⁩ و ⁦(0, 0)⁩ ← ⁦(0, 8)⁩ ئەوەندە درێژن؟Because the maze has no shorter pathچونکە لابیرینتەکە ڕێگەی کورتتری نییەBecause diagonal moves are not allowedچونکە جووڵەی لار ڕێگەپێدراو نییەBecause the program uses DFS, which returns the first path it findsچونکە بەرنامەکە DFS بەکار دەهێنێت، کە یەکەم ڕێگە دەگەڕێنێتەوە کە دەیدۆزێتەوە

Letting the user choose start and endڕێگەدان بە بەکارهێنەر سەرەتا و کۆتایی هەڵبژێرێت

Three problems in the input checkسێ کێشە لە پشکنینی نێوخستەدا

The lab reads each typed number with eval() (the third problem below) and then checks the two cells like this:

تاقیگەکە هەر ژمارەیەکی نووسراو بە eval() دەخوێنێتەوە (کێشەی سێیەمی خوارەوە) و پاشان هەردوو خانەکە بەم شێوەیە دەپشکنێت:

The lab's original check — do not copyپشکنینە ڕەسەنەکەی تاقیگە — کۆپیی مەکەPYTHON

# start and end are the two cells the user typed
if (start.x > len(maze) or start.y > len(maze[0]) or (maze[start.x][start.y] == "#")) or (
        end.x > len(maze) or end.y > len(maze[0]) or (maze[end.x][end.y] == "#")) or (
        (start.x == end.x) and (start.y == end.y)):
    print("Invalid Input. Try again.")

Three bugs in this checkسێ باگ لەم پشکنینەدا

1. > instead of >=: row 5 passes the check and maze[5][0] crashes with IndexError. 2. Negative numbers pass: -1 -1 is accepted, because Python reads maze[-1] as the last row. 3. eval() runs whatever the user types as Python code. Why these are dangerous, and the fix (int(), try/except and the full range check 0 <= x < len(maze)), is explained in The negative-index trap and Never use eval() on input. A reusable reader is built in A safe input function: get_int().

1. > لەبری >=: ڕیزی 5 لە پشکنینەکە تێدەپەڕێت و maze[5][0] بە IndexError دەشکێت. 2. تێدەپەڕن: -1 -1 وەردەگیرێت، چونکە maze[-1] وەک دوایین ڕیز دەخوێنێتەوە (). 3. eval() هەر شتێک بەکارهێنەر بینووسێت وەک کۆدی جێبەجێ دەکات. بۆچی ئەمانە مەترسیدارن و چارەسەرەکەیان (int()، try/except و پشکنینی تەواوی مەودا 0 <= x < len(maze)) لە تەڵەی ئیندێکسی سالب و هەرگیز ⁦eval()⁩ بۆ نێوخستە بەکار مەهێنە ڕوون کراوەتەوە. خوێنەرێکی دووبارە بەکارهاتوو لە کردارێکی نێوخستەی سەلامەت: ⁦get_int()⁩ دروست دەکرێت.

Letting the user choose start and endڕێگەدان بە بەکارهێنەر سەرەتا و کۆتایی هەڵبژێرێت

A safe versionوەشانێکی پارێزراو

The fixed program keeps the lab's search and messages but reads each cell with a small function, read_cell(), that returns None for anything that is not a valid open cell. It works like the reader in A safe way to read a cell.

چاککراوەکە گەڕان و پەیامەکانی تاقیگە دەهێڵێتەوە، بەڵام هەر خانەیەک بە بچووک دەخوێنێتەوە بە ناوی read_cell()، کە بۆ هەر شتێک کە خانەیەکی کراوەی دروست نەبێت None دەگەڕێنێتەوە. وەک خوێنەرەکەی ڕێگایەکی پارێزراو بۆ خوێندنەوەی خانەیەک کار دەکات.

Maze DFS with validated inputDFSی لابیرینت لەگەڵ پشتڕاستکردنەوەی نێوخستەmaze_input.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f"({self.x}, {self.y})"


def solve(maze, wall, start, end):
    directions = [
        (-1, 0), (0, -1), (1, 0), (0, 1),       # up, left, down, right
        (-1, -1), (-1, 1), (1, -1), (1, 1),     # diagonal movements
    ]
    frontier = [start]
    seen = [[False for _ in row] for row in maze]
    parent = {start: None}  # each point -> the point it came from

    while frontier:
        current = frontier.pop()
        if current.x == end.x and current.y == end.y:
            return backtrack(parent, current)
        seen[current.x][current.y] = True
        for dx, dy in directions:
            x, y = current.x + dx, current.y + dy
            if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] != wall and not seen[x][y]:
                nxt = Point(x, y)
                frontier.append(nxt)
                parent[nxt] = current
    return []


def backtrack(parent, current):
    path = []
    while current:
        path.append(current)
        current = parent.get(current)
    return path[::-1]


def read_cell(maze, prompt):
    """Read 'row column' from the user. Return a Point, or None if the input is not valid."""
    parts = input(prompt).split()
    if len(parts) != 2:
        return None
    try:
        x, y = int(parts[0]), int(parts[1])  # int(), never eval()
    except ValueError:                       # e.g. "a b"
        return None
    if not (0 <= x < len(maze) and 0 <= y < len(maze[0])):  # also rejects -1
        return None
    if maze[x][y] == "#":                    # a wall
        return None
    return Point(x, y)


maze = [
    "...##....",  # 0
    ".#...####",  # 1
    ".#.#....#",  # 2
    "##.##.##.",  # 3
    "....#....",  # 4
]

while True:
    start = read_cell(maze, "Enter (x, y) of start: ")
    end = read_cell(maze, "Enter (x, y) of end: ")
    if start is None or end is None or (start.x == end.x and start.y == end.y):
        print("Invalid Input. Try again.")
    else:
        print("Path found:", solve(maze, "#", start, end))
        break

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 17

A dictionary from each point to the point it came from.

لە هەر خاڵێکەوە بۆ ئەو خاڵەی لێوەی هاتووە.

Lineدێڕی 33-38

backtrack() follows parent.get() until None (the start).

backtrack() parent.get() دەگرێت تا None (سەرەتا).

Lineدێڕی 44-45

Exactly two values are needed.

ڕێک دوو نرخ پێویستە.

Lineدێڕی 46-49

int() instead of eval(); text such as a b raises ValueError, which we catch.

int() لەبری eval()؛ دەقێکی وەک a b ValueError دەردەکات، کە دەیگرین.

Lineدێڕی 50-51

The full range check: rejects 5, and also −1.

پشکنینی تەواوی مەودا: 5 ڕەت دەکاتەوە و ⁦−1⁩یش.

Lineدێڕی 52-53

A wall is not a valid start or end.

دیوار سەرەتا یان کۆتاییەکی دروست نییە.

BFS: a guaranteed shortest pathBFS: کورتترین ڕێگە بە گەرەنتییەوە

All the Lab 2 programs use DFS. To get a shortest route, use breadth-first search (why BFS finds the fewest steps). One solve() can do both if the frontier is a deque: pop() makes it a stack (DFS) and popleft() makes it a queue (BFS). Both modes below use the same rules as the lab code, and the cells are plain (row, column).

هەموو تاقیگەی ⁦2 DFS⁩ بەکار دەهێنن. بۆ بەدەستهێنانی ، بەکار بهێنە (بۆچی BFS کەمترین هەنگاو دەدۆزێتەوە). یەک solve() دەتوانێت هەردووکیان بکات ئەگەر deque بێت: pop() دەیکات بە ⁦(DFS)⁩ و popleft() دەیکات بە ⁦(BFS)⁩. هەردوو شێوازەکەی خوارەوە هەمان یاساکانی کۆدی تاقیگە بەکار دەهێنن و خانەکان سادەی (row, column)ن.

One solver, two frontiersیەک چارەسەرکەر، دوو بەرەmaze_bfs.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

from collections import deque

FOUR = [(-1, 0), (0, -1), (1, 0), (0, 1)]                # up, left, down, right
EIGHT = FOUR + [(-1, -1), (-1, 1), (1, -1), (1, 1)]      # + the diagonals


def solve(maze, start, end, mode, directions):
    """mode "DFS": the frontier is a stack. mode "BFS": the frontier is a queue.
    Cells are (row, column) tuples. Returns (path, number of cells expanded)."""
    frontier = deque([(start, None)])  # (cell, the cell we came from)
    parent = {}                         # cells already expanded -> their parent
    while frontier:
        current, came_from = frontier.pop() if mode == "DFS" else frontier.popleft()
        if current in parent:           # expanded before: skip it
            continue
        parent[current] = came_from
        if current == end:
            path = []
            while current is not None:
                path.append(current)
                current = parent[current]
            return path[::-1], len(parent)
        for dx, dy in directions:
            x, y = current[0] + dx, current[1] + dy
            if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] != "#" and (x, y) not in parent:
                frontier.append(((x, y), current))
    return [], len(parent)


maze = [
    "...##....",  # 0
    ".#...####",  # 1
    ".#.#....#",  # 2
    "##.##.##.",  # 3
    "....#....",  # 4
]

for end in [(4, 8), (4, 0), (0, 8)]:
    for mode in ["DFS", "BFS"]:
        path, expanded = solve(maze, (0, 0), end, mode, EIGHT)
        print(f"{mode} (0, 0) -> {end}: {len(path) - 1} moves, {expanded} cells expanded")
print()
path, _ = solve(maze, (0, 0), (4, 8), "BFS", EIGHT)
print("BFS path:", path)

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 3-4

Four moves, or eight with the diagonals.

چوار جووڵە، یان هەشت لەگەڵ لارەکان.

Lineدێڕی 10-11

The frontier holds (cell, parent) pairs; parent remembers every expanded cell.

جووتی (خانە، باوک) هەڵدەگرێت؛ parent هەموو خانەیەکی فراوانکراو لە بیر دەگرێت.

Lineدێڕی 13

The only difference between the two searches.

تاکە جیاوازیی نێوان دوو گەڕانەکە.

Lineدێڕی 14-15

A cell can be in the frontier twice; the second copy is skipped.

خانەیەک دەکرێت دوو جار لە بێت؛ وێنەی دووەم جێدەهێڵرێت.

Lineدێڕی 22

The number returned is how many cells were expanded, the goal included.

ئەو ژمارەیەی دەگەڕێنرێتەوە ژمارەی ئەو خانانەیە کە فراوان کران، ئامانجیشی تێدایە.

Read the output. BFS always finds the shortest route: 8, 6 and 8 moves. DFS finds 9, 9 and 16 moves — exactly the lab's results. Sometimes DFS expands fewer cells (18 against 28), sometimes more (25 against 22): it can be quicker, but its route can be poor. A plain list with pop(0) would also work; deque.popleft() is just the fast queue (A list as a stack or a queue).

دەرئەنجامەکە بخوێنەوە. BFS هەمیشە دەدۆزێتەوە: 8، 6 و 8 جووڵە. ⁦DFS 9⁩، 9 و ⁦16⁩ جووڵە دەدۆزێتەوە — ڕێک ئەنجامەکانی تاقیگە. هەندێک جار DFS خانەی کەمتر فراوان دەکات (⁦18⁩ بەرامبەر ⁦28⁩)، هەندێک جار زیاتر (⁦25⁩ بەرامبەر ⁦22⁩): دەکرێت خێراتر بێت، بەڵام ڕێگەکەی دەکرێت خراپ بێت. لیستێکی سادە لەگەڵ pop(0)یش کار دەکات؛ deque.popleft() تەنها خێراکەیە (لیست وەک ستاک یان کیوو).

Quick checkپشکنینی خێراWhich change turns this DFS solver into BFS?کام گۆڕانکاری ئەم چارەسەرکەرە DFSـە دەکات بە BFS؟Remove the parent dictionaryفەرهەنگی باوکەکان لاببەUse frontier.popleft() instead of frontier.pop()frontier.popleft() لەبری frontier.pop() بەکار بهێنەAdd the diagonal movesجووڵە لارەکان زیاد بکە

Common mistakesهەڵە باوەکان

Mistakeهەڵە	Fixچارەسەر
Printing the explored list and calling it the path.چاپکردنی و ناونانی بە ڕێگە.	Store parents and follow them back from the end.باوکەکان هەڵبگرە و لە کۆتاییەوە بەدوایاندا بگەڕێوە.
Calling a DFS path “optimal”.ناونانی ڕێگەیەکی DFS بە «باشترین».	Use BFS (equal costs) or UCS/A* (different costs) for a shortest path.بۆ ، BFS (کۆستی یەکسان) یان ⁦UCS/A⁩* (کۆستی جیاواز) بەکار بهێنە.
`x > len(maze)` as the range check.`x > len(maze)` وەک پشکنینی مەودا.	`0 <= x < len(maze)` (and the same for y).`0 <= x < len(maze)` (و هەمان شت بۆ y).
Forgetting that −1 is a valid index in Python.لەبیرکردنی ئەوەی ⁦−1⁩ لە دروستە.	Reject negative numbers explicitly. بە ڕوونی ڕەت بکەرەوە.
`eval(input())` for numbers.`eval(input())` بۆ ژمارە.	`int(...)` inside `try`/`except ValueError`.`int(...)` لە ناو `try`/`except ValueError`.
Using a global `seen` grid made after the function.بەکارهێنانی خانەبەندیی `seen`ی گشتی کە دوای دروست کراوە.	Create `seen` inside `solve()`.`seen` لە ناو `solve()`دا دروست بکە.
Curly quotes copied from a document.کۆتەیشنی خوار کە لە بەڵگەنامەیەکەوە کۆپی کراوە.	Type straight quotes `"` and `'`.کۆتەیشنی ڕاست بنووسە `"` و `'`.

Exercisesڕاهێنانەکان

ExerciseڕاهێنانFour directionsچوار ئاڕاستە

In maze_bfs.py, run the three searches with FOUR instead of EIGHT. How many moves do DFS and BFS need for (4, 8) and (4, 0)? What happens with (0, 8)?

لە maze_bfs.pyدا، سێ گەڕانەکە بە FOUR لەبری EIGHT جێبەجێ بکە. DFS و BFS بۆ ⁦(4, 8)⁩ و ⁦(4, 0)⁩ چەند جووڵەیان پێویستە؟ بۆ ⁦(0, 8)⁩ چی ڕوودەدات؟

Show answerوەڵامەکە پیشان بدە

Outputدەرئەنجام

DFS (0, 0) -> (4, 8): 12 moves, 15 cells expanded
BFS (0, 0) -> (4, 8): 12 moves, 23 cells expanded
DFS (0, 0) -> (4, 0): 8 moves, 22 cells expanded
BFS (0, 0) -> (4, 0): 8 moves, 16 cells expanded
DFS (0, 0) -> (0, 8): -1 moves, 24 cells expanded
BFS (0, 0) -> (0, 8): -1 moves, 24 cells expanded

With four directions both find 12 and 8 moves. (0, 8) cannot be reached without diagonals: the search expands all 24 reachable cells and returns an empty path, so len(path) - 1 prints −1. A real program should print “No path found.” instead.

بە چوار ئاڕاستە هەردووکیان ⁦12⁩ و 8 جووڵە دەدۆزنەوە. ⁦(0, 8)⁩ بەبێ جووڵەی لار ناگاتێ: گەڕانەکە هەموو ⁦24⁩ خانە گەیشتنپێکراوەکە فراوان دەکات و ڕێگەیەکی بەتاڵ دەگەڕێنێتەوە، بۆیە len(path) - 1 ژمارەی ⁦−1⁩ چاپ دەکات. ڕاستەقینە دەبێت لەبری ئەمە «⁦No path found⁩.» چاپ بکات.

ExerciseڕاهێنانHelpful error messagesپەیامی هەڵەی بەسوود

Improve read_cell() so that it tells the user why the input is wrong: “type two numbers”, “outside the maze” or “that cell is a wall”.

read_cell() باشتر بکە بۆ ئەوەی بە بەکارهێنەر بڵێت بۆچی هەڵەیە: «دوو ژمارە بنووسە»، «لە دەرەوەی » یان «ئەو خانەیە دیوارە».

Show answerوەڵامەکە پیشان بدە

The new read_cell() — the rest of maze_input.py is unchanged⁦read_cell()⁩ی نوێ — باقیی ⁦maze_input.py⁩ وەک خۆیەتیPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def read_cell(maze, prompt):
    """Read 'row column'. Say what is wrong and return None, or return a Point."""
    parts = input(prompt).split()
    try:
        if len(parts) != 2:
            raise ValueError
        x, y = int(parts[0]), int(parts[1])
    except ValueError:
        print("Please type two whole numbers, for example: 0 0")
        return None
    if not (0 <= x < len(maze) and 0 <= y < len(maze[0])):
        print("That cell is outside the maze.")
        return None
    if maze[x][y] == "#":
        print("That cell is a wall.")
        return None
    return Point(x, y)

Checking len(parts) first means parts[1] is never read when the user types only one number. The general “Invalid Input” line is still printed after each wrong pair.

پشکنینی len(parts) لە پێشدا واتە parts[1] هەرگیز ناخوێنرێتەوە کاتێک بەکارهێنەر تەنها یەک ژمارە دەنووسێت. دێڕە گشتییەکەی «⁦Invalid Input⁩» هێشتا دوای هەر جووتێکی هەڵە چاپ دەکرێت.

ExerciseڕاهێنانBlock the mazeداخستنی لابیرینتەکە

Look at the maze. If the cell (2, 5) became a wall, would there still be a path from (0, 0) to (4, 8) with four directions?

سەیری بکە. ئەگەر خانەی ⁦(2, 5)⁩ ببوایە بە دیوار، ئایا بە چوار ئاڕاستە هێشتا ڕێگەیەک لە ⁦(0, 0)⁩ەوە بۆ ⁦(4, 8)⁩ دەبوو؟

Show answerوەڵامەکە پیشان بدە

No. Row 3 has only three open cells. (3, 2) leads only to the bottom-left part, which the wall at (4, 4) cuts off; (3, 8) can be reached only from (4, 8) itself, because (2, 8) is a wall. So every route to the goal goes through (2, 5) → (3, 5), and with (2, 5) blocked the solver returns an empty list.

نەخێر. ڕیزی 3 تەنها سێ خانەی کراوەی هەیە. ⁦(3, 2)⁩ تەنها دەچێتە بەشی خوارەوەی چەپ، کە دیوارەکەی ⁦(4, 4)⁩ دەیبڕێت؛ ⁦(3, 8)⁩ تەنها لە ⁦(4, 8)⁩ـەوە دەتوانرێت پێی بگەیت، چونکە ⁦(2, 8)⁩ دیوارە. کەواتە هەموو ڕێگەیەک بۆ ئامانج بە ⁦(2, 5)⁩ ← ⁦(3, 5)⁩دا تێدەپەڕێت و کاتێک ⁦(2, 5)⁩ داخرا، چارەسەرکەرەکە لیستێکی بەتاڵ دەگەڕێنێتەوە.

Summaryپوختە

The maze is a list of strings; a cell is (row, column) and maze[x][y] reads it.
A move adds [dx, dy]; a move is allowed if it stays inside, is not a wall and was not seen.
The explored list is not the path; parent links (or a parent dictionary) give the path.
DFS returns the first path it finds, which may be long; BFS returns a shortest path when all moves cost the same.
Validate user input with int(), a full range check and try/except; never use eval().

لیستێکە لە ؛ خانەیەک (ڕیز، ستوون)ە و maze[x][y] دەیخوێنێتەوە.
جووڵەیەک [dx, dy] زیاد دەکات؛ جووڵە ڕێگەپێدراوە ئەگەر لە ناوەوە بمێنێتەوە، دیوار نەبێت و پێشتر نەبینرابێت.
ڕێگەکە نییە؛ پەیوەندیی باوکەکان (یان باوکەکان) ڕێگەکە دەدەن.
DFS یەکەم ڕێگە دەگەڕێنێتەوە کە دەیدۆزێتەوە و لەوانەیە درێژ بێت؛ BFS دەگەڕێنێتەوە کاتێک هەموو جووڵەکان هەمان کۆستیان هەبێت.
بە int()، پشکنینی تەواوی مەودا و try/except پشتڕاست بکەرەوە؛ هەرگیز eval() بەکار مەهێنە.

Review questionsپرسیارەکانی پێداچوونەوە

What is the difference between the explored list and the path?جیاوازیی نێوان کۆمەڵەی پشکنراو و ڕێگەکە چییە؟

The explored list has every cell the search visited, dead ends included. The path has only the cells from the start to the end.

هەموو ئەو خانانەی تێدایە کە گەڕانەکە سەردانی کردوون، ڕێگە داخراوەکانیشەوە. ڕێگەکە تەنها خانەکانی نێوان سەرەتا و کۆتایی تێدایە.

Why does the stack version reverse the directions list?بۆچی وەشانی ستاک لیستی ئاڕاستەکان پێچەوانە دەکاتەوە؟

A stack gives back the last item first, so reversing the list makes the intended first direction come out first.

دوایین دانە لە پێشدا دەداتەوە، بۆیە پێچەوانەکردنەوەی لیستەکە وا دەکات ئەو ئاڕاستەیەی دەمانەوێت یەکەم بێت لە پێشدا دەربچێت.

Which two inputs crashed or fooled the lab's input check?کام دوو نێوخستە پشکنینەکەی تاقیگەیان شکاند یان هەڵخەڵەتاند؟

5 0 crashed it (IndexError, because of >), and -1 -1 was accepted (negative index).

5 0 شکاندی (IndexError، بەهۆی >) و -1 -1 وەرگیرا ().

Videoڤیدیۆ

Watch a videoسەیری ڤیدیۆیەک بکە

A video that viewers liked a lot and praised in their comments, chosen for this lesson.ڤیدیۆیەک کە بینەران زۆریان پێ خۆش بووە و لە کۆمێنتەکانیاندا ستایشیان کردووە، بۆ ئەم وانەیە هەڵبژێردراوە.

Search - Lecture 0 - CS50's Introduction to Artificial Intelligence with Python 2020CS50 · Englishئینگلیزی · 190K viewsبینین · 3.8K likesلایک · Partبەشی 25:57–53:18 (ofلە 1:49:29)
Harvard's CS50 AI lecture on search: the parts of a search problem, the frontier loop, DFS and BFS on mazes, and greedy best-first search.
وانەی گەڕان لە کۆرسی ⁦CS50 AI⁩ـی زانکۆی Harvard: بەشەکانی ، ، و لەسەر ، هەروەها .
Watch 25:57-53:18 (a long overview): DFS with a stack, BFS with a queue, both solving mazes, and a walk through the Python maze program. In a maze every step costs 1, so the shortest path is also the cheapest.
لە ⁦25:57⁩ تا ⁦53:18⁩ سەیر بکە (پوختەیەکی درێژە): بە و بە ، کە هەردووکیان چارەسەر دەکەن، پاشان بە هەنگاو بە هەنگاو ڕوون دەکاتەوە. لە کۆستی هەر هەنگاوێک یەکە، بۆیە هەرزانترینیشە.

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

Depth-Limited, Uniform-Cost, Iterative Deepening and Bidirectional Searchگەڕانی قووڵایی سنووردار، گەڕانی کەمترین کۆست، گەڕانی قووڵکردنەوەی پلەبەپلە و گەڕانی دووئاڕاستە

Related lecturesوانە پەیوەندیدارەکان

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.