Problem 821. Pentago: find winning move

Created by Matthew Eicholtz

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Pentago\"><w:r><w:t>Pentago</w:t></w:r></w:hyperlink><w:r><w:t> 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</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>then</w:t></w:r><w:r><w:t> 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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:i/></w:rPr><w:t>board</w:t></w:r><w:r><w:t> - 6x6 matrix of filled with 0-2</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:i/></w:rPr><w:t>pos</w:t></w:r><w:r><w:t> - 1x2 vector with row and column of winning move (if any).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:i/></w:rPr><w:t>rot</w:t></w:r><w:r><w:t> - 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,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[rot = [-1 0\n 0 0]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>means the top-left game block was rotated 90 degrees in the counterclockwise direction.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[rot = [0 0\n 0 1]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>means the bottom-right game block was rotated 90 degrees in the clockwise direction.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[board = 0 0 0 0 2 0\n 1 1 1 2 1 0\n 0 0 0 0 0 0\n 0 2 0 2 0 0\n 0 1 0 0 0 0\n 0 0 0 0 0 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>should return</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[pos = [3 5]\nrot = [0 1\n 0 0]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>because placing a marble at (3,5) yields</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[0 0 0 0 2 0\n1 1 1 2 1 0\n0 0 0 0 1 0\n0 2 0 2 0 0\n0 1 0 0 0 0\n0 0 0 0 0 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>and then rotating the top-right block CW yields</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[0 0 0 0 2 0\n1 1 1 1 1 2\n0 0 0 0 0 0\n0 2 0 2 0 0\n0 1 0 0 0 0\n0 0 0 0 0 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>which gives Player 1 the win with 5 in a row (see 2nd row).</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

<a href="http://en.wikipedia.org/wiki/Pentago">Pentago</a> 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:<ul><li>board - 6x6 matrix of filled with 0-2</li></ul>Output:<ul><li>pos - 1x2 vector with row and column of winning move (if any).</li><li>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,</li></ul><pre class="language-matlab">rot = [-1 0
 0 0] 
</pre>means the top-left game block was rotated 90 degrees in the counterclockwise direction.<pre class="language-matlab">rot = [0 0
 0 1]
</pre>means the bottom-right game block was rotated 90 degrees in the clockwise direction.Example<pre class="language-matlab">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
</pre>should return<pre class="language-matlab">pos = [3 5]
rot = [0 1
 0 0]
</pre>because placing a marble at (3,5) yields<pre class="language-matlab">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
</pre>and then rotating the top-right block CW yields<pre class="language-matlab">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
</pre>which gives Player 1 the win with 5 in a row (see 2nd row).

Solve

Solution Stats

51 Solutions
20 Solvers

Last Solution submitted on Aug 21, 2020

Last 200 Solutions

Problem Recent Solvers20

Problem Tags

Problem 821. Pentago: find winning move

Solution Stats

Last 200 Solutions

Problem Recent Solvers20

Suggested Problems

More from this Author44

Problem Tags

Problem 821. Pentago: find winning move

Solution Stats

Last 200 Solutions

Problem Recent Solvers20

Suggested Problems

More from this Author44

Problem Tags

Players