1. rfc
  2. futoshiki_solver

Overview

HTTPS SSH
futoshiki solver

http://en.wikipedia.org/wiki/Futoshiki

futoshiki puzzle rules are encoded as a MIP

Variables

suppose puzzle is a grid of N*N cells
each cell holds a digit 1, ..., N.
there are N * N * N binary variables ("does cell i,j hold digit k?")

There are four kinds of problem constraints:

1.  for each group of cells (row or col), for each digit, there is one instance of the digit in the group
2.  for each cell, there is one digit in the cell
3.  for each pair of adjacent cells subject to an inequality, the digits in those cells must obey the inequality
4.  the digits in some cells may be fixed.

Pulp is used to solve the MIP via its built-in CBC solver.