# ABC - A Blokus Commitment

Welcome to Blokus, a board game where you can place pieces of 1 to 5 blocks on a square board.
Each player has at his disposal every piece from monomino to pentomino.

A player's inventory is composed of 21 pieces, accumulating 89 squares in total : All of these polyminoes are free, this means that you can rotate or flip them as you wish before placing them on the board.

The rules

Now what do we have to do in this puzzle ? Let's pick 2 natural numbers $k$ and $n$, and we'll try to place our pieces on a ($n*n$) square board to have exactly $k$ squares in each row and each column.

That gives us the following constraints :

• $0 < n$
• $0 < k \le n$
• $k*n \le 89$ (total number of placeable blocks)

Another rule is that each placed polymino musn't touch by the edge another polymino of the same color. It can however touch its corners, or the edges of an opponent's polymino.

For example, here are some possible cases of ($k,n$) done with 1 player :

(1,1) (2,2) (2,3) (2,4)  (2,5)   (3,5)
+-    +--   +---  +----  +-----  +-----
|P    |BB   |P W  |VV    |BB     |LLL
|BB   | WW  |V  W  |BB     |L  VV
|WW   |  WW  |   WW  | SS V
| WW   |  WW   |SS T
|  W P  |  TTT


Some example done with 2 players :

(3,3) (3,4) (4,4)
+---  +---- +----
|vvv  |LLL  |VVVp
|BBv  |vv L |VzzQ
|BBv  |v tL |VzQQ
| ttt |zzQQ


And some impossible cases for 1 player :

• ($n,n$) for $n>2$ : we would need a single piece of $n^2$ blocks (which is impossible), since any other piece that is composed of less blocks will create un-fillable blanks around its edges when placed.
• ($1,n$) for $n>1$ : you would need $n$ monominoes, which a single player has not in its inventory (and no, don't tear the blocks apart from others pieces, that's just brutal)

also :

• $k=4$, the 5-line piece can't be placed, total of placeable blocks for each player is $84$.
• $k=3$, the 4-line tetromino, the long L pentomino and the Y pentomino can't be placed either, this reduces the total placeable blocks for each player to $70$
• $k=2$, Only 6 pieces can be placed, and W is the only pentomino. total of placeable blocks for each player is $19$.

Scoring :

After completing a ($k,n$) board, the score will be evaluated as follows :

$$P = p1^2 + p2^2 + p3^2 + p4^2$$ $$Score = P/U * M$$

• $pX$ is the number of placed block from the inventory of player $X$
• $U$ is the number of players involved in completing the board (placed blocks > 0)
• For the record, $U>0$, because $k>0$
• Also, $U\le 4$
• $M$ is a bonus multiplier
• $M=1$ if $U=1$, or at least two pieces of different colors share an edge.
• $M=1.5$ if $U>1$ and no pair of pieces of any color share an edge.

The challenges :

• Maximize $(k,n) = (5, 10)$
• Maximize $(k,n) = (3, 20)$

I have found some scores on these that I believe can be optimized. But I'm actively trying to find out if the score on these 2 particular problems can or can not be completed using 1 player's inventory (which wields the best score)

And if you have found any perfect ($k,n$) boards (completed with only 1 player's set), don't hesitate to put them here.

• You could have at least put some link for your inspiration – Kalissar Jun 7 '16 at 12:45
• Pretty sure in the original game, your next piece has to be corner to corner with at least one of your existing pieces, I assume from your examples that you are allowing piece placement that violates this. – Arth Jun 22 '16 at 12:15
• @Arth Indeed. Here, every pair of same coloured piece can be connected to the corners, but it isn't an obligation, and if it was, it would have made the (3,20) board impossible, right away. – Anton Jun 22 '16 at 12:22
• See my answer for a $(k,n) = (3,20)$ with one player's pieces (not sure if adding solutions to my original post through edits triggers a new notification, so I'm throwing in this comment to make sure it doesn't get missed). – Steve Eckert Jul 25 '16 at 21:20

## Perfect board for $(k,n) = (3,20)$:

I did my diagram in Excel, since that was easier to disguise as real work at the office. I'll continue adding more if/when I find them.

    AA.................B
AA.................B
A....C.............B
....CC....D.........
.....CC...D.........
.........DDD........
..............E.FF..
.............EE.F...
.............E.FF...
..G....HH...........
.GGG................
..G...I..J..........
........JJ.....K....
.............KKK....
......LLL...........
...MM..L............
...MM.......N.......
............N....OO.
...........NN.....O.
...........N.....OO.


$Score = 60^2 = 3,600$

## $(k,n) = (4,9)$

    ..AA..BB.
.AA..C.B.
...CCC.B.
.DD.C.E..
DD....E.F
D....EE.F
..G..E.FF
H..II...F
HH.II....


## $(k,n) = (4,10)$

    AAA......B
AA..C....B
..CCC..D..
....C.DDD.
EEEE......
E...FF.G..
.....FF.HH
...I.F..HH
.III..J...
.....JJJJ.


## $(k,n) = (4,11)$

    AA...BB....
AA...BB....
A......C.DD
...E...CC.D
..EEE.....D
..E...F.GG.
.....FF..GG
....FF.HH..
IIII.......
....J..KKK.
.JJJJ......


• Good job on the (3, 20)! – Wesley Situ Jul 25 '16 at 21:21
• Well, I can stop trying now... I hope both of you (Steve and @WesleySitu) had a fun time doing this. the (5,10) and (3, 20) boards really left me hopeless at some point. :) – Anton Jul 25 '16 at 23:41
• We could theoretically go up to $(3,23)$, so if you'd like to keep looking at that, feel free :P – Steve Eckert Jul 25 '16 at 23:58

## $k = 2$ : possible for $n\in 2..9$

Combined with the (2, 2), (2, 3), (2, 4) and (2, 5) in the first post, this is complete, as $n \geq 10$ requires $k \cdot n \geq 20$ blocks, but if $k = 2$ only 19 blocks can be placed (as stated in the question).

(2,6) plain text version:

.AA...
AA....
A..B..
..BB..
....CC
....CC


(2,7)

A...B..
...BB..
..BB...
.....CC
.....CC
.DD....
DD.....


(2,8)

AA......
AA......
..BB....
..B....C
......CC
.....CC.
...DD...
....DD..


(2,9)

.AA......
.....BB..
.....BB..
CC.......
C......D.
.......DD
....E...D
...EE....
..EE.....


## $k = 3$, so far, solutions have been found when $n = 5..9$

(3,6)

AAA...
A..BB.
A...BB
.CCC..
.C.C.E
..D.EE

And for the style : diagonals also have a 3 out of 6 completion.

(3,7)

A.BB...
....CCC
DD...C.
DD..E..
....EEE
..FF..E
.FFF...


(3,8)

..AA..C.
..AA.D..
BB...D..
B....D.E
....F.EE
....F.EE
.G.FF...
GGG.....


(3,9)

AAA......
A.A.B....
...BB.D..
..BB..D..
.....DDD.
GG......E
.G.....EE
.....F.EE
...FFF...


## $k=4$

(4,4), (4,5), (4,6) are impossible, because there is not enough holes to separate the pieces.

(4,7)

AA.B.D.
A.C..DD
A.CCC..
A..C.EE
.GG.F.E
.GG.F.E
.G.FFF.


(4,8)

.AA..BB.
AA....BB
.A..CC.B
D..E.CC.
D.EEE...
DD.E.F..
..G.G.HH
..GGG..H


(this community wiki answer is used to show the current progress)

## Solutions

$(5,10)$ Perfect

$(5,10)$ incomplete $P = 48^2 + 2^2 = 2308$
$Score = (2308/2)*1.5 = 1731$

($3,20$) incomplete $P = 56^2 + 4^2 = 3152$
$Score = 3152/2*1.5 = 2364$

## Board Tileset ## Operating on a board

How to manipulate squares on a board without messing up the numbers of blocks in the rows & columns ?
(These operations below aren't practicable on a real board)

Shift all the squares in the same direction, and loop those which exit the board.

Swap 2 squares ($A$ and $B$) :
if the squares on the location $(X_A, Y_B)$ and $(X_B, Y_A)$ are empty,
then you can remove $A$ and $B$ and place the squares on these new locations.

• Nice diagrams & tileset. But how did you create the diagrams? – Rosie F Jun 17 '16 at 18:20
• @RosieF I used Graphics gale, using custom grid snapping and copy pasting. – Anton Jun 17 '16 at 18:33
• Thanks, @Anton. I had a quick look at the web site. It looks as if using that software to produce such images would be extremely complicated and time-consuming. – Rosie F Jun 17 '16 at 19:00
• @RosieF I guess using the tileset (or just rects) and simple PowerPoint is a quick and easy alternative... – BmyGuest Jun 21 '16 at 22:15
• Never mind -- I found that Ghostgum's GSview can save in PNG format. (Full page, but Paint can crop the image). And I already know enough PostScript to program what I need. Thank you for your suggestions anyway. – Rosie F Jun 22 '16 at 5:53