Problem 113. N-Queens Checker

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:r><w:t>Picture a chessboard populated with a number of queens (i.e. pieces that can move like a queen in chess). The board is a matrix, a, filled mostly with zeros, while the queens are given as ones. Your job is to verify that the board is a legitimate answer to the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Eight_queens_puzzle\"><w:r><w:t>N-Queens problem</w:t></w:r></w:hyperlink><w:r><w:t>. The board is good only when no queen can \"see\" (and thus capture) another queen.</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>The matrix below shows two queens on a 3-by-3 chessboard. The queens can't see each other, so the function should return TRUE.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 1 0 0\n 0 0 1\n 0 0 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Here is a bigger board with more queens. Since the queens on rows 3 and 4 are adjacent along a diagonal, they can see each other and the function should return FALSE.</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 1\n 1 0 0 0\n 0 0 1 0 \n 0 1 0 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The board doesn't have to be square, but it always has 2 or more rows and 2 or more columns. This matrix returns FALSE.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 1 0 0 0 0 \n 0 0 0 1 1]]></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>"}]}

Solve

Solution Stats

658 Solutions
161 Solvers

Last Solution submitted on Oct 29, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 547461

1 Comment

1 Comment

yurenchu on 12 Mar 2017

Only works because test suite isn't extensive enough. Wouldn't work with a = [1 0 1; 0 0 0; 0 1 0], for example.

Solution 439776

1 Comment

1 Comment

yurenchu on 12 Mar 2017

Cheating solution.

Solution 253926

1 Comment

1 Comment

Jan Orwat on 26 Sep 2013

This solution has a minor bug, but it fortunately passed the test suite. :-)

Solution 90576

2 Comments

2 Comments

yurenchu on 12 Mar 2017

It's supposed to be a n-QUEENS checker, not an n-KINGS checker. This solution wouldn't work with a = [1 0 1; 0 0 0; 0 1 0], for example.

Ned Gulley on 15 Mar 2017

Thanks yurenchu! I added your proposed test point to the tests.

Solution 8234

2 Comments

2 Comments

Alfonso Nieto-Castanon on 27 Jan 2012

test suite needs additional samples that fail due to diagonal movements (e.g. [1,0;0,1])

Ned Gulley on 30 Jan 2012

I added this test. Rescoring now. Thanks for the suggestion.

Problem Recent Solvers161

Problem Tags

game

Community Treasure Hunt

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

Start Hunting!

Problem 113. N-Queens Checker

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers161

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Problem 113. N-Queens Checker

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers161

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players