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 Jun 7, 2016 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, 2016 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. Jun 22, 2016 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). Jul 25, 2016 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.

Plaintext:

    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)$

Plaintext:

    ..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)$

Plaintext:

    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)$

Plaintext:

    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)! Jul 25, 2016 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. :) Jul 25, 2016 at 23:41
• We could theoretically go up to $(3,23)$, so if you'd like to keep looking at that, feel free :P Jul 25, 2016 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)

in plain text:

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


(2,8)

in plain text:

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


(2,9)

in plain text:

.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)

in plain text:

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)

in plain text:

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


(3,8)

in plain text:

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


(3,9)

in plain text:

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)

in plain text:

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


(4,8)

in plain text:

.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$

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? Jun 17, 2016 at 18:20
• @RosieF I used Graphics gale, using custom grid snapping and copy pasting. Jun 17, 2016 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. Jun 17, 2016 at 19:00
• @RosieF I guess using the tileset (or just rects) and simple PowerPoint is a quick and easy alternative... Jun 21, 2016 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. Jun 22, 2016 at 5:53