Problem 821. Pentago: find winning move

Pentago is a challenging two-player strategy game. The objective is to be the first player to connect five marbles in a row (horizontally, vertically, or diagonally) on the board. The 6x6 board consists of four 3x3 game blocks, each of which can be twisted in 90-degree intervals (CW/CCW). During a turn, a player places a marble anywhere on the board and then rotates one of the game blocks 90 degrees in either direction. The marble does not have to be played on the same block that is rotated.

For this problem, you are given a 6x6 matrix representing the current board setup, where 0s, 1s, and 2s correspond to empty spaces, Player 1 marbles, and Player 2 marbles, respectively. You are Player 1 and it is your turn. If there is a winning move, return the row and column subscripts of the winning play as well as the required rotation (see below for details). If you can win without rotating a game block, return [] for the second output. If there is no winning move on this turn, both outputs should be []. You may assume that there will be only one winning move, if any.

Input:

• board - 6x6 matrix of filled with 0-2

Output:

• pos - 1x2 vector with row and column of winning move (if any).
• rot - 2x2 matrix describing rotation required to win (if any). A CW rotation is indicated by a 1, while a CCW rotation is indicated by a -1. For example,

rot = [-1 0
        0 0]   

means the top-left game block was rotated 90 degrees in the counterclockwise direction.

rot = [0 0
       0 1]

means the bottom-right game block was rotated 90 degrees in the clockwise direction.

Example

board = 0 0 0 0 2 0
        1 1 1 2 1 0
        0 0 0 0 0 0
        0 2 0 2 0 0
        0 1 0 0 0 0
        0 0 0 0 0 0

should return

pos = [3 5]
rot = [0 1
       0 0]

because placing a marble at (3,5) yields

0 0 0 0 2 0
1 1 1 2 1 0
0 0 0 0 1 0
0 2 0 2 0 0
0 1 0 0 0 0
0 0 0 0 0 0

and then rotating the top-right block CW yields

0 0 0 0 2 0
1 1 1 1 1 2
0 0 0 0 0 0
0 2 0 2 0 0
0 1 0 0 0 0
0 0 0 0 0 0

which gives Player 1 the win with 5 in a row (see 2nd row).