Field-Programmable Gate Arrays (FPGAs) have adopted and successfully adapted a variety of ASIC layout techniques. Iterative improvement placers [4], maze-style[191 and channel-style routers [161 are extremely common here. But the discrete nature of FPGA logic blocks and routing fabrics also admits unique layout strategies that each strives to leverage the limited palette of geometric alternatives to prune the space of viable layouts. Search-based global and detailed routers [3][5], channel routers 1151, and simultaneous placer/routers [22][28] are a few examples of such attacks that actually exploit the rigid limitations on FPGA layout geometries. Unfortunately, these geometric limitations still render the problem of predicting whether a given netlist can fit on a specific FPGA architecture--in particular, whether it can route successfully after placement--very difficult. Improvements in routability estimators [6], statistical estimators [lo], simultaneous placer/routers [22], and routing tactics that can heuristically abandon the layout when unroutability appears inevitable [27] are all viable responses to this critical problem. Nevertheless, it remains a practical impossibility to answer exactly this simple question for most FPGA placements: is this layout routable?