How many 8-step walks on a grid trace out just a unit square in the lower-right quadrant?

walk.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "98/65536\n",
      "210/65536\n"
     ]
    }
   ],
   "source": [
    "def paths(pos,seen,steps,must_end_at_origin = True):\n",
    "    x,y = pos\n",
    "    seen |= 2**(2*x+y)\n",
    "    #print(\"{}at {},{}, seen {}\".format('  '*(4-steps),x,y,bin(seen)[2:]))\n",
    "    if steps==0:\n",
    "        #print('{}{}'.format('  '*(4-steps),seen==2**4-1))\n",
    "        return seen==2**4-1 and (not must_end_at_origin or x==y==0)\n",
    "    \n",
    "    vecs = ((1,0),(-1,0),(0,1),(0,-1))\n",
    "    t = 0\n",
    "    for dx,dy in vecs:\n",
    "        nx,ny = x+dx,y+dy\n",
    "        if nx in (0,1) and ny in (0,1):\n",
    "            t += paths((nx,ny),seen,steps-1,must_end_at_origin)\n",
    "    return t\n",
    "            \n",
    "print('{}/{}'.format(paths((0,0),0,8,must_end_at_origin=True),4**8))\n",
    "print('{}/{}'.format(paths((0,0),0,8,must_end_at_origin=False),4**8))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1+"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}