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

640 Solutions
220 Solvers

Last Solution submitted on Sep 23, 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 Solvers220

Problem Tags

game

Problem 113. N-Queens Checker

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers220

Suggested Problems

More from this Author50

Problem Tags

Problem 113. N-Queens Checker

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers220

Suggested Problems

More from this Author50

Problem Tags

Players