  P\'olya's random walk theorem states that a random walk on a $d$-dimensional
grid is recurrent for $d=1,2$ and transient for $d\ge3$. We prove a version of
P\'olya's random walk theorem for non-backtracking random walks. Namely, we
prove that a non-backtracking random walk on a $d$-dimensional grid is
recurrent for $d=2$ and transient for $d=1$, $d\ge3$. Along the way, we prove
several useful general facts about non-backtracking random walks on graphs. In
addition, our proof includes an exact enumeration of the number of closed
non-backtracking random walks on an infinite 2-dimensional grid. This
enumeration suggests an interesting combinatorial link between non-backtracking
random walks on grids, and trinomial coefficients.
