Home Puzzles arithmetic – Fitting pentominoes inside a 10×10 grid

arithmetic – Fitting pentominoes inside a 10×10 grid

0
arithmetic – Fitting pentominoes inside a 10×10 grid

[ad_1]

Bonus:

The most variety of distinct free pentominoes is $12$:

W.YYYY.UUU
WW.Y...U.U
.WW.NNN.X.
T..NN..XXX
TTT..FF.X.
T..ZZ.FF.I
.PP.Z.F..I
PPP.ZZ.V.I
...L...V.I
LLLL.VVV.I

I used integer linear programming as follows. Introduce binary choice variable $x_p$ for every potential placement of a pentomino within the grid. Let binary choice variable $y_{ij}$ point out whether or not cell $(i,j)$ is an orthogonal neighbor of a minimum of one chosen pentomino. Let $P_{ij}$ be the set of pentominoes that comprise cell $(i,j)$. Let $N_p$ be the set of cells that neighbor pentomino $p$. The unique downside is to maximise $sum_p x_p$ topic to
start{align}
sum_{pin P_{ij}} x_p + y_{ij} &le 1 &&textual content{for all $(i,j)$} tag1label1
x_p &le y_{ij} &&textual content{for all $p$ and $(i,j)in N_p$} tag2label2
finish{align}

Constraint eqref{1} prevents cell $(i,j)$ from showing in a couple of chosen pentomino and from each showing in a single chosen pentomino and neighboring a specific pentomino.
Constraint eqref{2} forces $y_{ij}=1$ for all cells $(i,j)$ that neighbor chosen pentomino $p$.

For the bonus downside, let $t_p$ be the sort (F,I,L,N,P,T,U,V,W,X,Y,Z) of pentomino $p$, and let binary choice variable $z_t$ point out whether or not a minimum of one pentomino of kind $t$ is chosen. The downside is to maximise $sum_t z_t$ topic to eqref{1}, eqref{2}, and
start{align}
z_t &le sum_{p: t_p = t} x_p &&textual content{for all $t$} tag3label3
finish{align}

Constraint eqref{3} forces some pentomino of kind $t$ to be chosen if $z_t=1$.

[ad_2]

LEAVE A REPLY

Please enter your comment!
Please enter your name here