Patent Document ID: 7904867
Application ID: 11732848
Patent Flag: 1

Claim One:
1. A system that routes electrical connections during the design of an integrated circuit (IC) chip, comprising: a routing engine configured to search for a current path to electrically connect a current pair of points in a set of pairs of points; a routing database used by the routing engine, which keeps track of objects that can obstruct the routing of the current pair of points; and a satisfiability (SAT) solver capable of solving a set of constraints, which are associated with the routability of the set of pairs of points, wherein the SAT solver includes a SAT database which maintains the set of constraints and a current partial solution to the set of constraints, wherein the SAT database is configured to update the routing database if the current partial solution changes, and wherein the routing engine invokes the SAT solver to examine the current path before searching for a next path to electrically connect a next pair of points in the set of pairs of points.