Google OR-Tools

Constraint Programming

Project implementations utilizing the Google OR-Tools packages for constraint programming.

Goal

This repository contains projects that make use of the Google OR-Tools constraint programming package. It is intended to showcase implementations of constraint programming to solve various combinatorial problems.

Package Installation

Install ortools

$ python -m pip install --upgrade --user ortools

Install numpy

$ pip install numpy

OR-Tools Specifications

Constraints define the unique and specific properties of a solution we want to be found. Listed below are constraints that are used throught these project implementations:

• Add - adds a BoundedLinearExpression to the model
• AddAllDifferent - forces all variables provided as input to have different values

Statuses are descriptions of the results of the model being tested. There are five possible statuses:

• INFEASIBLE - returned when it is proven that no solutions are to be found.
• FEASIBLE - returned when some solutions are found.
• OPTIMAL - returned when all solutions have been found.
• MODEL_INVALID - returned when the model does not pass the validation step.
• UNKNOWN - returned when a search limit is reached and no solution has been found.

Project Descriptions

• Cryptarithmetic - The Cryptarithmetic Puzzle Solver takes some n number of words in from user input. For the n words, all words up to the (n-1)th word will sum up to equal the (n)th word.

  • Create word and letter arrays - The program first reads each string for the left-hand side and right-hand sides of the equations. It generates a word_array (contains whole words) and a split_word_array (a list of lists where each list contains split words).
  • Creating the variables - To obtain a NewIntVar integer variable for each unique letter in the equation, the program iterates through each character in each word of the split word array and adds the { character : NewIntVar } key-value pair to the letters_dict.
  • Define and add constraints - The AddAllDifferent constraint is applied to intvar_array, which is the values set of letters_dict, to ensure that each unique letter has a unique value. The Add constraint is applied to the equation generated in the for loop that iterates through the split word array. The inner for loop creates a numerical value for each particular word by generating a digit for each place value, which is then added to the constraint array.
  • Generate and call the solution - Generate the solution using cp_model.CpSolver() and call back the solution found for each unique letter - showing all possible solutions for the puzzle.
  • Provide runtime statistics - The program provides the user with insight to the program by outputting the status, the number of conflicts, the number of search branches, the time the program took to complete, and the total number of solutions found.

• Magic Squares - The Magic Squares Solver takes a magic square, the normality of the puzzle, and the magic sum for a non-normal puzzle as user input. The user enters n rows and n colums of values separated by spaces, where blank spaces are entered as 0 and preset spaces are entered as the given number.

  • Get normality and size of puzzle - Ask the user if the puzzle for the size of the puzzle and if it is normal or not - this affects what the magic sum of the puzzle will be. A normal puzzle contains values restricted to the range [1, n²] and is solved with the magic sum calculated using the formula: M_n = [n(n²+1)] / 2. A non-normal puzzle is contains values restricted to no range and is solved with a magic sum specified by the user.
  • Create a matrix of all variables - The program creates a matrix of size n composed of uniquely identified NewIntVar integer variables.
  • Define and add constraints - The Add constraint is applied to the Magic Square to ensure that the summation of each row, column, and diagonal equals the magic sum.
    • Rows - iterate through each row of the matrix stored as a NumPy array to add each row contraint
    • Columns - iterate through each row of the transpose of the matrix (i.e. the columns of the original matrix) stored as a NumPy array to add each column constraint
    • Diagonals - add the constraint to each diagonal using the diagonal() method on the original matrix and the reflection of the matrix obtained using the np.fliplr function
  • Generate and call the solution - Generate the solution using cp_model.CpSolver() and call back the solution found for each block of the Magic Square. From a list of all n² variables, split the list into equal sections of 9 values using the equal_parts method created, and output each row to generate the completed Magic Square.
  • Provide runtime statistics - The program provides the user with insight to the program by outputting the status, the number of conflicts, the number of search branches, the time the program took to complete, and the total number of solutions found.

• N-Queens - The N-Queens Solver takes a number n as user input. The program solves the puzzle by finding placements of the n queens on an n x n chessboard such that no two queens are threatening each other.

• Sudoku Solver - The Sudoku Solver takes a 9x9 Sudoku puzzle as user input. The user enters nine rows and nine columns of values separated by spaces, where blank spaces are entered as 0 and preset spaces are entered as the given number.

  • Create a matrix of all variables - The program first creates uniquely identified NewIntVar integer variables and organizes them in a 9x9 NumPy matrix.
  • Define and add constraints - The AddAllDifferent constraint is applied to the Sudoku puzzle to fill unique values of 1-9 in each row, column, and 3x3 subsquare. To add each constraint:
    • Rows - iterate through each row of the matrix stored as a NumPy array to add each row constraint
    • Columns - iterate through each row of the transpose of the matrix (i.e. the columns of the original matrix) stored as a NumPy array to add each column constraint
    • Subsquares - iteratively create 3x3 slices for each subsquare in each three-row set and three-column set and add each subsquare constraint
  • Generate and call the solution - Generate the solution using cp_model.CpSolver() and call back the solution found for each block of the Sudoku puzzle. From a list of all 81 variables, split the list into equal sections of 9 values using the equal_parts method created, and output each row to generate the completed Sudoku Puzzle.
  • Provide runtime statistics - The program provides the user with insight to the program by outputting the status, the number of conflicts, the number of search branches, the time the program took to complete, and the total number of solutions found.