Write a function to verify whether an arrangement of queens on a chessboard is a valid solution to the classic eight queens problem.
In the eight queens problem, eight queens must be placed on a chessboard such that no two queens attack each other. That is, no two queens can share the same row, column, or diagonal. The diagram below is one possible solution:
Your function should take an 8-by-8 matrix of 0s and 1s, where the 1s represent the position of the queens, and return a logical 1 if the solution is valid or a logical 0 otherwise.
EXAMPLE 1
in1 = [ ... 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 ];
isEightQueensSolution(in1)
returns 1.
EXAMPLE 2
in2 = [ ... 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 ];
isEightQueensSolution(in2)
returns 0. (Notice that the queens on the bottom two rows share a diagonal.)
This question is kind of a duplicate of Ned's N-queens checker: http://www.mathworks.com/matlabcentral/cody/problems/113-n-queens-checker
Oops, I didn't know about that one!
This is a flawed solution. For example, when the queen positions are {a2, b4, c2, c6, d8, e3, f1, g7, h5} (which is the same as the image in the description, but with a 9th queen added at c2), this code would return 'True' while the correct answer is obviously 'False'.
The beauty of this solution is that you can use it for any other side board (e.g., isEightQueensSolution([1 0; 0 1]) ).
how can i view this solution, also, can you please explain to me why the tenth test case is false, i dont think it is wrong.
Alex, the tenth case case is false because there are only seven queens on the board.
Doesn't this kind of trick get boring after a while?
actually, this is the first time i've used it without essentially copying Alfonso's code, so it's still new and fresh for me =P
Can someone explain to me how this function works (even if it is a trick)? I'm trying to parse through the code, but how it works isn't clear to me.
the sparse function places the values (third input) into the row and column specified, 1st and second inputs respectively. if there are any overlapping coordinates then it sums them, so I created a matrix that, when fed into sparse, would sum the rows, sum the columns, and sum the diagonals in each direction. Then I Cody-fied it (teehee) by changing these indices into a string of characters, which Cody sizes as small, and subtracting a base character from it. does that make sense now?
it might make more sense to look at one of my other solutions that uses the str2num function instead of the letter thing...
I think you also need to check the diagonals of fliplr(a). The tests did not include multiple queens on any of those diagonals.
749 Solvers
210 Solvers
The Hitchhiker's Guide to MATLAB
2696 Solvers
Project Euler: Problem 4, Palindromic numbers
123 Solvers
134 Solvers