To answer this, we’ll further define what we mean by product configuration, look at what the challenges of configuration are, and see how Configit solves those challenges with its patented Virtual Tabulation (VT) technology.
What are Interactive Product Configurators?
Interactive product configuration is the process by which users, often customers, use software called configurators to customize products to their specific needs. A configurator shows the user which features of a product can be customized (for example, ‘interior color’), and what the possible values for each feature are (‘red’, ‘green’, ‘blue’, etc.).
When the user chooses a value, the configurator restricts the remaining possible values of the other features so that the product’s rules are enforced. The user keeps selecting values until only one configuration remains; each feature has a value selected.
What are the challenges of interactive product configuration?
A configurator must prevent users from choosing invalid values – ones that are not part of a valid solution. The configurator must also allow users to reach every possible valid solution (known as the solution space).
These properties are often difficult to achieve in traditional configurators, which are based on ‘constraint propagation’ logic. They run into problems such as:
- Exposing the user to ‘dead ends’, where some features end up not having any valid choices
- Backtracking, where the user is forced to go back to a previous step in the configuration
- Hiding values or preventing the user from selecting values that should be selectable
Complete interactive product configurators – ones that know the entire solution space up front – can solve these problems.
What does a backtrack-free and complete configurator look like?
We can illustrate the power of a backtrack-free and complete configurator using a classical chess puzzle called the 8-queen problem: place 8 queens on a chessboard so that no two queens share the same row, column, or diagonal.
The number of different ways to place the eight queens is enormous: 4,426,165,368 ways. Only 92 of these are solutions to the 8-queens problem.
With the support of a configurator, you can quickly solve this problem. Say you place the first queen at position A5. The configurator then marks the positions that are not valid, guiding the user to only valid solutions (see the screenshot below, to the left). Notice that position E6 is marked as invalid, even though a queen at E6 would not threaten the queen at A5. This is because the configurator knows that there are no possible valid configurations with a queen on both A5 and E6.
Now say you place the next queen at H8. The configurator automatically places the remaining queens because it knows the entire solution space, and, in this case, there is only a single valid configuration remaining.
How does Configit solve these configuration challenges?
Making interactive product configurators that are complete and backtrack-free is quite difficult. If you express the rules of the product model using the Boolean operators “and”, “or” and “not”, then the rule set is functionally complete and can express any Boolean expression. It follows that the configuration problem is NP-complete, meaning it is inherently difficult and may require computing resources that are exponential to the size of the product model.
Configit’s approach is to represent product model rules in graphs called binary decision diagrams (BDDs). These graphs are combined into a ‘Virtual Table’ which compactly stores all legal combinations of features and their values – that is, the complete solution space. Once the solution space is known, interactive product configurators can easily guide users to valid configurations, and backtracking is eliminated as users will never be put in a situation where there are no values to choose from.
Using BDDs has proven to be a very effective approach for solving the configuration problem. You can learn more in the paper “Comparing Two Implementations of a Complete and Backtrack-Free Interactive Configurator”, which shows how the BDD-based approach outperforms a configuration engine from iLog by several orders of magnitude. See the paper “Virtual Tabulation” for more details on how BDDs are used to solve the configuration problem.