Patent Document ID: 9898567
Application ID: 14629303

Base Claim:
1. A computer implemented method of legalizing a circuit layout for manufacturing a circuit, the circuit layout using a plurality of non-uniform grids, the circuit layout comprised of a layout object, the method comprising: generating a set of layout constraints for the layout object based on the plurality of non-uniform grids, the set of layout constraints comprising design rule check constraints and gridding requirements, the gridding requirements being requisites for the layout object to align to one of the plurality of non-uniform grids, the layout object having layout variables to identify a position of the layout object; processing the set of layout constraints to a feasible form for the layout object to be modified to satisfy the set of layout constraints by: assigning Boolean variables to the layout variables, each Boolean variable from the Boolean variables assigned to a corresponding layout variable from the layout variables, determining whether the set of layout constraints is infeasible using the Boolean variables assigned to the layout variables, and responsive to the set of layout constraints determined to be infeasible, (i) identifying an infeasible layout constraint from the set of layout constraints, the infeasible layout constraint causing the set of layout constraints to be infeasible, and (ii) relaxing the identified infeasible layout constraint for the set of layout constraints to be in the feasible form; and generating, by solving the set of layout constraints in the feasible form with a linear program solver, an output circuit layout to provide for manufacture of the circuit.

---

Claim 2:
2. The method of claim 1 , wherein identifying the infeasible layout constraint from the set of layout constraints comprises: generating a Boolean implication graph based on the Boolean variables, the Boolean implication graph modeling a possible position of the layout object, and determining satisfiability of the Boolean implication graph.