A tool to explore how to model a constraint satisfaction problem with an engine for solving it and presenting a solution. Uses the Google or-tools for solving the problem.
The program idea is outlined in The strange case of the missing application. The Workbench is an attempt to build the missing application, to see if such a thing exists, or has any utility. In the past whenever I've tried to come up with a suitable interface I've always eventually come up with something a lot like a spreadsheet. Just goes to show just how good a paradigm the spreadsheet is.
Plainly a big barrier to any kind of constraint satisfaction project is going to be the fact that they are NP-hard problems. In other words, they tend to be very hard to solve quickly. I'm kind of working on the assumption that Moore's Law is going to rescue me. All of those hundreds or thousands of CPU cores we are supposed to be getting over the next decade or so should help. Quantum computers should help a lot too. So, I am just going to assume that, at some point in the future, the hardware will be there to solve even very complex constraint satisfaction problems in a reasonable amount of time.
- Technical level - the user of the software should require a technical level at or below that of an average spreadsheet user;
- Build a playground - the user should be able to model various types of constraint problems and then able to solve them in an interactive manner and present the results;
- Solution display - should be configurable, taking a technical model and displaying the resulting solution in a manner that makes sense to the user;
- No programming - absolutely no programming. There are plenty of development environments available, there is no need to build yet another one here;
- Optimization - The user should be able to optimize the solution interactively.
The image below is a picture of the model used to solve the n-queens problem produced by version 0.4. As you can see the application supports aggregate variables, expression and all different constraints and domains.
You can also create a solution. When I say a solution I don't mean just a set of values that represent one state that satisfies all of the constraints. I mean you can design how your solution is displayed in very rudimentary ways. Currently there are two ways of displaying a solution, a chess board and a table.
The most egregious failing of the project manifesto to date is the breach of the no programming rule. There plainly is quite a lot of what looks suspiciously like programming in the various languages included in the project. The most obvious being the visualizer binding language. I have a few ideas how I can reduce the level of programming in the visualizer bindings but I doubt I can remove it altogether.
Please do not use this project for anything other than experimentation. I make no guarantees about backward compatibility or indeed anything else. The project is currently just a prototype. It may well never be anything beyond that.
- C#
- Google or-tools - CSP library amongst many other things
- WPF
- Caliburn Micro
- Irony - used to build the parsers
- NUnit - unit test framework
- Jack Hughes - Initial work - digitalbricklayer
Constraint Capers Workbench is licensed under a BSD license.
Many thanks to Ashley Davies for writing NetworkView: A WPF custom control for visualizing and editing networks, graphs and flow-charts upon which the prototype of the model display is based.
Thanks also to David Hopkins for the edit icon used in the program. The original can be found here.