Functional verification of complex designs largely relies on the use of simulation in conjunction high-level verification languages (HVL) and test-bench automation (TBA) tools. In a constraints-based verification methodology, constraints are used to model the environmental restrictions of the Design Under Verification (DUV), and are specified using HVL constructs. The job of a constraints solver is to produce multiple random solutions to these constraints. These random solutions are used to drive legal random stimulus to the DUV using procedural HVL constructs. This paper presents RACE (Random ATPG for solving Constraint Expressions), a new word-level engine for solving combinational constraint expressions. RACE builds a high-level netlist model to represent the constraints and implements a branch-and-bound algorithm to solve them. Advanced interval arithmetic concepts and algorithms are used to propagate word-level values across a wide variety of high-level operators. RACE is architected to produce multiple random solutions for the same constraints problem, and has been successfully used for random stimulus generation within a commercial TBA tool [14] for Register Transfer Level (RTL) verification of complex designs using simulation.