"Visited" vs "Seen" Positions in Breadth-First Search
I recommend you to take the same approach as I did to draw my conclusions: take a graphical approach to see the differences and drawbacks.

For that, do the following:


Comment out all print lines except print("Frontier:", frontier)
Then do python program.py &gt; version1.txt, modify your program such that it represents verison 2, and then do python program.py &gt; version2.txt.
Get pen &amp; paper and draw a 4 × 4 table.


Here is a comparison of the first lines of both log files:

    Version 1           Version 2

Frontier: (4, 4)     Frontier: (4, 4)
Frontier: (3, 4)     Frontier: (3, 4)
Frontier: (4, 3)     Frontier: (3, 4)
Frontier: (2, 4)     Frontier: (4, 3)
Frontier: (3, 3)     Frontier: (2, 4)
Frontier: (3, 3)     Frontier: (4, 4)
Frontier: (4, 2)     Frontier: (3, 3)


I leave it as an exercise for you to draw this with pen &amp; paper. Can you take it from here?

Note that the duplicate (3, 4) is version 2 is suspicious. Can you guess where it comes from?


  I would like to know if there is a "canonical" version which is considered best practice.


You typically want the invariant that everything in the queue is already put in the seen queue. As a formula, this amounts to saying $$\text{work queue}\ \subseteq\ \text{seen queue}.$$

Otherwise, you could pick the tip of the work queue, say item $i_1$, go through its neighbors to then add its neighbor $i_2$ to the work queue. However, $i_2$ was already part of the work queue before (perhaps just after $i_1$!), but you couldn't know since you didn't keep the seen queue synchronized.

Hence, implementing this invariant amounts in your code to


putting start onto the seen queue

queue = collections.deque([[start]])
seen_or_visited = set([start])

choosing version 2, i.e.

seen_or_visited.add(next_pos) # Uncomment for version (2)



You may also want to comment out version 1, i.e.

#seen_or_visited.add(frontier) # Uncomment for version (1)


since the invariant, fulfilled by the two points above, guarantees that whatever you pick from the queue (here, frontier) has already been added to the seen queue.

By the way, your function is missing a return None in case it doesn't find the target position.