Patent Number: 
Section: claims

1. A computer-implemented method for resolving a design rule violation in a circuit design layout including a plurality of shapes, the method comprising:receiving data that indicates that an odd number of shapes form a loop in which each pair of neighboring-shapes has the pair's two shapes closer than a threshold distance;generating, using a processor, a set of design solutions based on the received data, each design solution for moving at least one shape of at least one pair of neighboring-shapes so that a distance between the pair of neighboring-shapes exceeds the threshold distance; andprioritizing the generated design solutions based on a certain set of criteria to select a generated design solution to apply to the design layout. 2. The method of claim 1 further comprising selecting the highest priority design solution that does not cause a new design rule violation. 3. The method of claim 1 further comprising computing a cost of applying each of the generated design solutions to the design layout, wherein the certain set of criteria includes costs computed for the generated design solutions. 4. The method of claim 3, wherein the cost relates to likelihood of the design solution to cause a new design violation when applied to the design layout. 5. The method of claim 3, wherein computing the cost of applying the generated design solution comprises:defining a set of regions based on a distance from the shape to move;assigning different costs to different shapes in different defined regions; andadding up the assigned costs. 6. The method of claim 3, wherein computing the cost of applying the generated design solution comprises computing a cost for each shape that would be within the threshold distance from the shape to move. 7. The method of claim 6, wherein the cost for each shape that would be within the threshold distance from the shape to move is computed based on the shape's distance from the moved shape. 8. The method of claim 6, wherein the cost for the shape that would be within the threshold distance from the shape to move is computed based on a type of the shape, wherein types of shapes comprise a regular shape, a via shape, and an instance shape. 9. The method of claim 3, wherein the cost of applying the generated design solution is computed based on a distance by which to move the at least one shape. 10. The method of claim 3, wherein computing the cost of applying the generated design solution comprises:determining whether a via shape has a non-overlapping portion with the shape to move; andwhen the via shape has a non-overlapping portion with the shape to move, adding an additional cost to the cost of applying the generated design solution. 11. The method of claim 1, wherein the certain set of criteria includes one criterion. 12. The method of claim 1, wherein the certain set of criteria includes two or more criteria. 13. A non-transitory machine readable medium storing a program for resolving a design rule violation in a circuit design layout including a plurality of shapes, the program comprising sets of instructions for:receiving data for indicating a double patterning loop comprising an odd number of shapes, wherein each particular shape in the double patterning loop is within a threshold distance of neighboring shapes in the double patterning loop;generating a set of design solutions based on the received data, each design solution for breaking the loop by moving at least one of the shapes in the double patterning loop;setting priorities to the generated design solutions based on a certain set of criteria; andusing the priorities to select a generated design solution for applying to the circuit design layout. 14. The non-transitory machine readable medium of claim 13, wherein the program further comprises a set of instructions for computing a cost of applying each of the generated design solutions to the circuit design layout, wherein the certain set of criteria includes costs computed for the generated design solutions. 15. The non-transitory machine readable medium of claim 14, wherein the cost of applying the generated design solution is computed based on a number of shapes that would be within the threshold distance from the shape to move. 16. The non-transitory machine readable medium of claim 15, wherein the set of instructions for computing the cost comprises a set of instructions for adjusting the cost based on types of the shapes that would be within the threshold distance from the shape to move. 17. The non-transitory machine readable medium of claim 15, wherein the set of instructions for computing the cost comprises a set of instructions for adjusting the cost based on a distance between the shape to move and the shapes that would be within the threshold distance from the shape to move. 18. The non-transitory machine readable medium of claim 14, wherein the set of instructions for computing the cost comprises sets of instructions for:identifying shapes that would be within the threshold distance from the shape to move;assigning a cost to each of the identified shapes; andadding up the assigned costs. 19. The non-transitory machine readable medium of claim 14, wherein shapes in the circuit design layout are grouped into a first set of shapes and a second set of shapes based on lithography masks on which the shapes are to be fabricated, wherein the set of instructions for computing the cost comprises sets of instructions for:defining a region of the design layout based on a position of the shape to move in the design layout;identifying shapes that fall within the defined region;assigning a cost to each of the identified shapes when all of the identified shapes and the shape to move belong to the first set;assigning a cost to each of the identified shapes when one of the identified shapes belongs to the first set and another of the identified shapes belongs to the second set;assigning no cost to each of the identified shapes when all of the identified shapes belong to the first set while the shape to move belongs to the second set;assigning no cost to each of the identified shapes when all of the identified shapes belong to the first set while the shape to move belongs to neither of the two sets; andadding the assigned costs to the cost of applying the generated design solution. 20. A system comprising:a processor for executing sets of instructions; anda memory for storing a computer program for correcting a design rule violation in a circuit design layout including a plurality of shapes, the program comprising sets of instructions for:receiving data for indicating a double patterning loop comprising number of shapes, wherein each particular shape is within a threshold distance of neighboring shapes in the double patterning loop;generating a set of design solutions based on the received data, each design solution for breaking the loop by moving at least one of the shapes in the double patterning loop; andselecting a generated solution that has a lowest likelihood of causing a new design rule violation when applied to the design layout. 21. The system of claim 20, wherein the program further comprises a set of instructions for modifying the design layout using the selected design solution. 22. The system of claim 20, wherein the program further comprises a set of instructions for quantifying a likelihood of causing a new design rule violation for each generated design solution when the generated design solution is applied to the design layout.