14
$\begingroup$

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 :

player's inventory in Blokus

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.

$\endgroup$
  • 3
    $\begingroup$ You could have at least put some link for your inspiration $\endgroup$ – Kalissar Jun 7 '16 at 12:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Arth Jun 22 '16 at 12:15
  • 1
    $\begingroup$ @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. $\endgroup$ – Anton Jun 22 '16 at 12:22
  • $\begingroup$ 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). $\endgroup$ – Steve Eckert Jul 25 '16 at 21:20
4
$\begingroup$

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.

enter image description here
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)$

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

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

enter image description here
Plaintext:

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

$\endgroup$
  • $\begingroup$ Good job on the (3, 20)! $\endgroup$ – Wesley Situ Jul 25 '16 at 21:21
  • $\begingroup$ 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. :) $\endgroup$ – Anton Jul 25 '16 at 23:41
  • $\begingroup$ We could theoretically go up to $(3,23)$, so if you'd like to keep looking at that, feel free :P $\endgroup$ – Steve Eckert Jul 25 '16 at 23:58
5
$\begingroup$

Perfect boards

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

2 6 perfect board
plain text version:

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

(2,7)

2 7 perfect board
in plain text:

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

(2,8)

2 8 perfect board
in plain text:

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

(2,9)

2 9 perfect board
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)

3 6 perfect board
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)

3 7 perfect board
in plain text:

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

(3,8)

perfect 3 8
in plain text:

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

(3,9)

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

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

perfect 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

$\endgroup$
5
$\begingroup$

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

Solutions

$(5,10)$ Perfect

huzzah!

$(5,10)$ incomplete

2 blocks shy of the ultimate win !
$P = 48^2 + 2^2 = 2308$
$Score = (2308/2)*1.5 = 1731$

($3,20$) incomplete

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

Board Tileset

template for blokus grid

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.

$\endgroup$
  • $\begingroup$ Nice diagrams & tileset. But how did you create the diagrams? $\endgroup$ – Rosie F Jun 17 '16 at 18:20
  • $\begingroup$ @RosieF I used Graphics gale, using custom grid snapping and copy pasting. $\endgroup$ – Anton Jun 17 '16 at 18:33
  • $\begingroup$ 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. $\endgroup$ – Rosie F Jun 17 '16 at 19:00
  • $\begingroup$ @RosieF I guess using the tileset (or just rects) and simple PowerPoint is a quick and easy alternative... $\endgroup$ – BmyGuest Jun 21 '16 at 22:15
  • $\begingroup$ 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. $\endgroup$ – Rosie F Jun 22 '16 at 5:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.