Jacop

Jacop is a fast constraint solver with powerful features for solving problems involving integers, sets of integers, and floats. The examples included here all relate to puzzles (my interest), but Jacop can of course be used more seriously. Two advantages of examples based around puzzles are that the problems are easy to understand and the coding is relatively short.

For more information on Jacop, see:

• the user guide;
• the API documentation;
• the discussion forum;
• academic papers on Jacop;
• its source code and JAR file.

A fabulous resource for programming with constraints in many different languages and libraries is hakank's Home Page. His Jacop page is here, and he also has a page for the Scala version of Jacop.

1. Cryptoarithmetic

A cryptoarithmetic puzzle is typically a single math expression (often involving addition) where the digits are represented by letters. Your task is to identify the unique digit (0 to 9) that goes with each letter.

• SendMoreMoney.java: the famous "SEND + MORE = MONEY" equation;
   
  
• DonaldGeraldRobert.java: the almost equally famous "DONALD + GERALD = ROBERT". The Jacop coding uses a slightly more fancy approach than in SendMoreMoney.java, involving weighted sums for the letters and the words;
   
  
• LeastDiff.java aims to find the smallest value for "ABCDE - FGHIJ", and so uses a cost parameter to constrain the search.
   
  

2. Logic Puzzles

This section contains a few logic grid puzzles, so named because they're best solved by drawing a grid to mark out the ways that data can be combined, and various combinations eliminated. For those of you interested in learning this approach, have a look here, here, and here.

• Zebra.java: the most famous puzzle of this type, often attributed to Einstein or Lewis Carroll. The coding strategy is to implement the puzzle categories as arrays and to link the categories by having their array cells use the same integer values (domains). Two cells in different arrays with the same integer value are considered 'equal';
   
  
• BabySitting.java: similar to Zebra.java, but a bit simpler since there are less conditions to encode;
   
  
• HistoricHomes.java: more complex than Zebra.java in that it requires Element constraints;
   
  

3. Grid-based Games

The game grid, or chessboard, means that the Jacop code must deal with constraints between the cells of a 2D array. The examples below are ordered simplest to hardest, with the main difference being the number of constraints applied to the grid cells.

• LatinSquare.java : a basic Latin Square problem consists of filling a square with numbers in such a way that every row and column doesn't contain two numbers with the same value;
   
  
• NQueens.java : place n queens on a n x n chessboard so none of the queens are in check;
   
  
• Sudoku.java : a Sudoku solver, but you'll have to edit the vals[] array to change the problem being solved;
   
  
• Kakuro.java : Kakuro puzzles supply row and column sums and the player must insert a digit into each empty cell so that the sum of the numbers in each row/column matches the row/column totals. Also, no digit can appear twice in any row or column.
   
  

Aside from the listed examples, I've utilized two support files: JacopUtils.java and ValsMap.java, which offer utilities for printing search results and manipulating arrays of variables.

Downloads and Other Links

• Batch files to easily compile and run my code: compile.bat and run.bat
   
  
• All the examples in one zipped file (24 KB).
   
  
• My copies of the Jacop library (1.91 MB): jacop-4.3.0.jar. Unzip the file, and place the libs folder in the same directory as the examples and batch files.
   
  
• The official library for Jacop.