Problem 2538. Find the Next Legal Move in Reversi

Created by Ned Gulley

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/Reversi\"><w:r><w:t>Reversi</w:t></w:r></w:hyperlink><w:r><w:t>, also known as Othello, is a game in which reversible white/black chips are placed on a grid. The goal is to have the most pieces once the board is full (i.e. there are no more legal moves). A move, to be legal, must flip at least one opponent's chip by flanking it. \"Flanking\" occurs by surrounding a line of opposing chips with two of your own. It can occur on straight lines and diagonals.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If we represent a small 4x4 board this way, with 0 for empty squares, 1 for black chips, and 2 for white chips,</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\n 0 1 2 0\n 0 2 1 0 \n 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>then black has 4 legal moves shown by b.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ [ 0 0 b 0\n 0 1 2 b\n b 2 1 0 \n 0 b 0 0 ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Any of these moves will flank (surround) a white chip and cause it to be flipped.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your Cody challenge is to take the given board (always square) and side (1 or 2) and locate all the legal moves. Return all legal moves as a vector of column-wise indices into the matrix. If there are no legal moves, return empty.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For the board shown above,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ side = 1 (black)\n moves = [3 8 9 14]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note: See also</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/2565-determine-the-result-of-a-move-in-reversi\"><w:r><w:t>Problem 2565</w:t></w:r></w:hyperlink><w:r><w:t>, Determine the Result of a Move in Reversi.</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/Reversi">Reversi</a>, also known as Othello, is a game in which reversible white/black chips are placed on a grid. The goal is to have the most pieces once the board is full (i.e. there are no more legal moves). A move, to be legal, must flip at least one opponent's chip by flanking it. "Flanking" occurs by surrounding a line of opposing chips with two of your own. It can occur on straight lines and diagonals.If we represent a small 4x4 board this way, with 0 for empty squares, 1 for black chips, and 2 for white chips,<pre> [ 0 0 0 0
 0 1 2 0
 0 2 1 0 
 0 0 0 0 ]</pre>then black has 4 legal moves shown by b.<pre> [ 0 0 b 0
 0 1 2 b
 b 2 1 0 
 0 b 0 0 ]</pre>Any of these moves will flank (surround) a white chip and cause it to be flipped.Your Cody challenge is to take the given board (always square) and side (1 or 2) and locate all the legal moves. Return all legal moves as a vector of column-wise indices into the matrix. If there are no legal moves, return empty.Example.For the board shown above,<pre> side = 1 (black)
 moves = [3 8 9 14]</pre>Note: See also <a href = "http://www.mathworks.com/matlabcentral/cody/problems/2565-determine-the-result-of-a-move-in-reversi">Problem 2565</a>, Determine the Result of a Move in Reversi.

Solve

Solution Stats

36 Solutions
13 Solvers

Last Solution submitted on Nov 12, 2019

Last 200 Solutions

Problem Comments

Solution Comments

Solution 495060

1 Comment

1 Comment

Ned Gulley on 20 Jan 2015

This code is referenced in the following blog post: http://blogs.mathworks.com/community/2015/01/19/robot-game-playing-in-matlab-part-2/

Problem Recent Solvers13

Problem Tags

game

Problem 2538. Find the Next Legal Move in Reversi

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers13

Suggested Problems

More from this Author49

Problem Tags

Problem 2538. Find the Next Legal Move in Reversi

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers13

Suggested Problems

More from this Author49

Problem Tags

Players