How to Cut your Board using CP?

Cutting the shapes has always fascinated mathematicians. In this episode of Optimization in Open Source , we focus on cutting a chessboard.

Introduction

Honestly, finding a good math problem is always a challenge for me, so I spend some of my spare time reading math books (such a NERD!). In one of these books, I stumbled upon this fascinating problem:

In simple words "How can we split the chess board into two equal surface parts? "

The point is that each part should be connected (horizontally or vertically).

Let me clarify the concept.

Two trivial ways of spliting is as follows:

but is there any other way to do it ? yes there is

How can we find all possible different ways of this cutting?

Alright, enough with the fluff—let's dive into the fun part: the math modeling!

Math model

The first essential constraint is to have enough numbe of cells in each slice (two slices in total). where U is a boolean variable indicating if the cell i should be black or not.

Then a more challenging constraint is to ensure the connectivity of black cells (slice 1). For this purpose I assume there is a single source in slice one (found by boolean variable B_i) and all other cells in slice 1 have a sink demand which should be supplied. Keeping in mind that the connectivity of two cells is checked with Z_ij (boolean) and the flow between them is indicated with flow?b_ij (integer).

• Const 1: is the nodal balance , 32Bi is the source at node i , U_i represents the demand at node i
• Const 2: The flow on blck cells is limited to 32 and if cell i is linked to cell j
• Const 3,4: Both node i and node j should be black to allow the black flow between them (Z?b_ij)
• Const 5: Just one cell is selected on the black cells as the source.

The same concept is applied to the white cells (slice 2).

if we miss constraints 6-10 in the model then the following solution might be obtained: You can see that the black cells are connected but the white cells have islands in them.

Finally, a cell can be a source for either black slice or white slice:

Ok, now let's look at the overall model:

As it can be observed, the model has no objective function and it's a pure constraint satisfaction. you can also see the obtaned solution. But what is the underneath of this visualization ? what is the rule of Z, flow , B, W ?

Let's have a deep dive into it. The red lines show the Zb and the blue ones are Zw. When creating the Zb,Zw elements, it should be noted that these variables should be only defined over the adjacent cells (up/dn/right/left cells).

Finished ? No the journey has just begun!

Is the obtained solution unique ?

The answer is no, but how to obtain them all ? It's simple, after obtaining the first answer th

following constraint is added to the model and it is resolved untiltehre is no solution found.

This guarantees that at least one cell will be filled differently in the next solution compared to the current one.

Here is the python code (also available in github)

Symmetry breaking

The introduced problem has some kind of symmetry which can be improved by adding extra constraints.

Conculsion

You might be wondering (or even asking me), "Why on earth would a wise person want to cut up a chessboard?" Well, get ready, because the answer is more fun than you might think!

• Modeling Skill: Translating a problem described in words into pure, hard-core math is an art form. Not everyone has this skill, but the good news is that it can be honed and developed with practice.
• Coding Skill: Solving a math-based model through coding can reveal both the gaps in your knowledge and the strengths of the programming language and optimization tools you're using.
• Visualization: Showcasing your project findings in a visual format is always a fun way to engage a diverse audience, regardless of their background.
• Storytelling and Dissemination: Sharing the journey and insights of your project through storytelling not only makes the information more accessible but also helps spread the knowledge effectively to a broader audience.

Git repo : https://github.com/OptimizationExpert/Pyomo