Problem 1701. Solve the picross! (Hard)

Created by Benoit Charles

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":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/image","targetMode":"","relationshipId":"rId1","target":"/media/image1.png"}],"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:r><w:t>Solve the picross!</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Nonogram\"><w:r><w:t>http://en.wikipedia.org/wiki/Nonogram</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The arguments (horz and vert) are cells containing the clues, e.g:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>horz = { 2, [1, 1], [] }; vert = { 2, 1, 1 };</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>means</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:customXml w:element=\"image\"><w:customXmlPr><w:attr w:name=\"height\" w:val=\"-1\"/><w:attr w:name=\"width\" w:val=\"-1\"/><w:attr w:name=\"relationshipId\" w:val=\"rId1\"/></w:customXmlPr></w:customXml></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You have to return the completed picross, a logical or double matrix with a 0 for a white case and a 1 for a black case. If we solve the previous example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:customXml w:element=\"image\"><w:customXmlPr><w:attr w:name=\"height\" w:val=\"-1\"/><w:attr w:name=\"width\" w:val=\"-1\"/><w:attr w:name=\"relationshipId\" w:val=\"rId1\"/></w:customXmlPr></w:customXml></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So, the output argument should be:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>picross = [ 1 1 0 ; 1 0 1 ; 0 0 0 ];</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You have to do some guessings and optimize your code to pass the test suite.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Have fun!</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>See also:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.fr/matlabcentral/cody/problems/1700-solve-the-picross-easy\"><w:r><w:t>http://www.mathworks.fr/matlabcentral/cody/problems/1700-solve-the-picross-easy</w:t></w:r></w:hyperlink></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>"},{"partUri":"/media/image1.png","contentType":"image/png","content":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAACAAAAAgCAMAAABEpIrGAAADAFBMVEV4eHiTk5P29vaBgYGcnJzAwMC3t7eKiorS0tLt7e3b29vk5OTJycn///9vb28AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD61b95AAAAyklEQVR42q2SSQ6FIAxAWzQxkcj976lEE5R+hojQOmw+Cxa8RwcoGnhf6oNDD0AvGL8j/E2wC+JiXwSaAKbbatGkLjBrX13szynmtPXnKc2eCRiMGQtXxrq2hmZRuuXx6SVdPlPpopeC387sFMMIwdsyAMFAEcHuptW5oIaKYgjHBBoZ512snMeJ8g7o0DmA5jwKXRdqy9W6gfMzhd7iMOySlxq0qn/z4leR43HNQ8WrLtYi1Dz+pnjsmt/8ZsulwLgQOOeC4EyQHH5z1GUZiLNTtwAAAABJRU5ErkJggg=="}]}

Solve

Solution Stats

6 Solutions
3 Solvers

Last Solution submitted on Nov 27, 2020

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

Richard Zapor on 9 Jul 2013

A good challenging task. Very nice input format of cell arrays.

Rafael S.T. Vieira on 27 Oct 2020

Solving a grid of 75x60 squares within Cody's time limit is extra hard. The greatest challenge is to find a fast code; recursion with backtracking no longer seems like a viable option. And I do hope the author is aware that nonograms are an NP-hard problem, which means there is no known fast algorithm to solve the general case: we have to build one for the specific cases of the test suite.

Rafael S.T. Vieira on 28 Oct 2020

To any new challengers, know that only logic will not solve these puzzles. You will need some guessing, which means make the computer solve it as far as it can and then you, yes YOU, look at the picture (we humans can recognize the shape and finish the puzzle; the computer not so much). And, please, fell free to try some solvers out there.

Problem Recent Solvers3

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1701. Solve the picross! (Hard)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers3

Suggested Problems

More from this Author1

Problem Tags

Community Treasure Hunt

Problem 1701. Solve the picross! (Hard)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers3

Suggested Problems

More from this Author1

Problem Tags

Community Treasure Hunt

Players