Verify the queens puzzle

Question

If you don't know what a queen is in chess, it doesn't matter much; it's just a name :)

Your input will be a square of arbitrary width and height containing some amount of queens. The input board will look like this (this board has a width and height of 8):

...Q....
......Q.
..Q.....
.......Q
.Q......
....Q...
Q.......
.....Q..

There are 8 queens on this board. If there were, say, 7, or 1, or 10 on here, the board wouldn't be valid.

Here we use a . for an empty space, and a Q for a queen. You may, alternatively, use any non-whitespace character you wish instead.

This input can be verified as valid, and you should print (or return) a truthy value (if it is was not valid, you should print (or return) a falsy value). It is valid because no queen is in the same row, column, diagonal or anti-diagonal as another.

Examples (don't output things in brackets):

...Q....
......Q.
..Q.....
.......Q
.Q......
....Q...
Q.......
.....Q..

1

...Q.
Q....
.Q...
....Q
..Q..

0

Q.
Q.

0

..Q
...
.Q.

0 (this is 0 because there are only 2 queens on a 3x3 board)


..Q.
Q...
...Q
.Q..

1

Q

1 (this is valid, because the board is only 1x1, so there's no queen that can take another)

Let me stress that an input is only valid, if no queen is in the same row, column, diagonal or anti-diagonal as another.

Rules

• You will never receive an empty input
• If the input contains fewer queens than the sqaure root of the area of the board, it is not valid.
• Note there are no valid solutions for a 2x2 or 3x3 board, but there is a solution for every other size square board, where the width and height is a natural number.
• The input may be in any reasonable format, as per PPCG rules
• The input will always be a sqaure
• I used 1 and 0 in the examples, but you may use any truthy or falsy values (such as Why yes, sir, that is indeed the case and Why no, sir, that is not the case)

As this is code-golf, the shortest code wins!

Answer 1

Snails, 14 bytes

&
o.,\Q!(z.,\Q

Try it online!

Nothing like a 2D pattern matching language for a 2D decision problem. :)

Explanation

The & on the first line is a match mode option which requires the pattern on the second line to match from every possible position in the input. If that's the case, the program prints 1, otherwise it prints 0.

As for the pattern itself, note that there's an implicit ) at the end.

o       ,, Move in any orthogonal direction (up, down, left or right).
.,\Q    ,, Make sure that there's a Q somewhere in that direction from the
        ,, starting position of the match.
!(      ,, After finding the Q, make sure that the following part _doesn't_ match:
  z     ,,   Move in any orthogonal or diagonal direction.
  .,\Q  ,,   Try to find another Q in a straight line.
)

Why this works is easiest to see by starting from the negative lookahead: by ensuring that there is no Q in a straight line from the other Q we've already found, we make sure that there are no more than N queens (otherwise, there would have to be two in one row, and it wouldn't be possible to find these queens without finding another). Then the first part, making sure that there's a queen reachable in an orthogonal direction from any position, makes sure that there are exactly N queens. If one was missing, there would be a row and a column without a queen. Starting from the intersection of these, it wouldn't be possible to find a queen by going only in an orthogonal direction.

Answer 2

Jelly, 17 or 15 bytes

ỴµUŒD;ŒD;ZVṀ;V=1Ṃ

Try it online!

Uses ‘ for a queen and ¹ for blank space. (This is mostly a consequence of the ban on taking input as an array, because it forces the input to be strings; converting strings to integers is difficult in Jelly, with the easiest method being evaluation, and it turns out that instead of 1 and 0, using "add 1" (‘) and "add 0" (¹) make it possible to omit several sum and map instructions, because we can count the queens in a list by evaluating it.) The truthy and falsey values are Jelly's normal 1 and 0.

EDIT: The question's been changed since I wrote this answer to allow taking input as a matrix. This allows dropping the leading Ỵµ, saving 2 bytes. It also probably allows changing the input format to something more normal, using S to sum rather than V to evaluate, but I don't think that saves bytes and I kind-of like this funky format.

Explanation

ỴµUŒD;ŒD;ZVṀ;V=1Ṃ
Ỵ                    Split on newlines.
 µ                   Set this value as the default for missing arguments.
     ;  ;            Concatenate the following three values:
  UŒD                - the antidiagonals;
      ŒD             - the diagonals;
         Z           - and the columns.
          V          Evaluate (i.e. count the queens on) all of those.
           Ṁ         Take the largest value among the results.
            ;V       Append the evaluation (i.e. queen count) of {each row}.
              =1     Compare each value to 1.
                Ṃ    Take the minimum (i.e. most falsey) result.

So the basic idea is that we ensure that there's at most one queen on each antidiagonal, diagonal, and column; and exactly one queen on each row. These conditions are together enough to require that there's at most one queen on each of the four sorts of line, and a number of queens equal to the side length of the board.

Incidentally, Jelly could probably do with a built-in for antidiagonals, but AFAICT it doesn't seem to have one, so I need to settle for reflecting the board and then taking the diagonals.

Another interesting note is that changing =1Ṃ to E (all equal) gives a generalized n-queens checker, which will also accept an n×n board where each row, column, diagonal, and antidiagonal contains no more than k queens, and the board contains exactly kn queens. Restricting k to equal 1 actually cost two bytes.

Answer 3

Octave, 57 70 67 51 52 bytes

Saved 1 byte using flip instead of rot90 thanks to @LuisMendo, but found a bug on the 1x1 case

@(A)all(sum([A A' (d=@spdiags)(A) d(flip(A))],1)==1)

Takes input as a binary matrix with 1 representing a Queen and 0 representing an empty space.

Creates an anonymous function that first concatenates the input matrix and its transpose.

spdiags creates a matrix with the same number of rows as the argument, with the diagonals turned into columns (zero-padded as necessary), so concatenate spdiags of the input matrix to get the diagonals and spdiags of the matrix flipped horizontally to get the antidiagonals.

Now take the sum of each column of the concatenated matrix and make sure each column is exactly 1.

Sample run on ideone.

Answer 4

MATL, 38 34 bytes

4 bytes off thanks to @beaker!

sG!sGt&n_w&:&XdsGP5M&Xdsv2<GnGzU=*

The input is a 2D array of zeros and ones, using semicolons as row separators.

This outputs a column vector of ones as truthy, and a column vector containing at least one zero as falsy.

Try it online! The footer code is an if branch to demonstrate truthiness or falsyhood.

Or verify all test cases.

Explanation

s      % Input binary matrix implicitly. Sum of columns. Gives a row vector
G!     % Paste input again. Transpose
s      % Sum of columns (rows in the original matrix). Gives a row vector
G      % Paste input again
t&n    % Duplicate. Push number of rows and number of columns (will be equal)
_w     % Negate, flip
&:     % Binary range. Gives [-n -n+1 ... n] for input of size n×n
&Xd    % Get diagonals -n through n. This gives all diagonals as colums
s      % Sum of each column (diagonals of original matrix). Gives a row vector
GP     % Paste input again. Flip vertically
5M     % Push [-n -n+1 ... n] again
&Xd    % Get diagonals -n through n (anti-diagonals of original matrix)
s      % Sum of each column. Gives a row vector
v      % Concatenate everything into a column vector
2<     % True for elements that are less than 2
Gn     % Paste input again. Number of elements
Gz     % Paste input again. Number of nonzeros (i.e. of queens)
U      % Square
=      % True if equal
*      % Mutiply, element-wise

Answer 5

SnakeEx, 67 bytes

m:({q<>}({q<R>}[{q<RF>}{n<RF>}].)*{e<>}<R>)%{4}
e:.$
q:_*Q_*$
n:_+$

Uses _ in place of . in the input. Returns 1 or more matches for truthy, 0 matches for falsey. You can find an online interpreter at the link in the header.

Explanation

SnakeEx is a language from the 2-D Pattern Matching challenge. It defines "snakes" that move around the grid matching stuff. Snakes can spawn other snakes, making the language quite powerful.

Let's look at this program from the bottom up.

n:_+$

This defines a snake n that matches 1 or more underscores and then the edge of the grid. Note that this may be in any of the 8 cardinal directions--the direction is determined when the snake is spawned.

q:_*Q_*$

Similar to n above, this defines q as a snake that matches any number of underscores, a single Q, any number of underscores, and the edge of the grid. In other words, a row/column/diagonal that has only one queen in it.

e:.$

e is a snake that matches one character and the edge of the grid.

m:({q<>}({q<R>}[{q<RF>}{n<RF>}].)*{e<>}<R>)%{4}

The main snake m uses these building blocks to check the whole board. Conceptually, it runs around the outside edges of the grid, spawning other snakes to check that all columns and rows have exactly one queen, and all diagonals have at most one queen. If any of the spawned snakes fails to match, the entire match fails. Let's break it down.

• ( )%{4} runs what's inside the parentheses 4 times, once for each side. (In what follows, it's helpful to picture a particular side--say, the top edge of the grid, starting from the top left corner and moving right.)
• {q<>} spawns a q snake in the same direction that the main snake is moving. This verifies that the current edge meets the "exactly one queen" rule. Note that spawned snakes do not move the main snake's match pointer, so we're still at the beginning of the edge.
• ( )* matches 0 or more of what's inside the parentheses.
• {q<R>} spawns a q snake turned rightward from the main snake's direction. (E.g. if the main snake is moving rightward along the top edge, this snake moves downward.) This checks each column/row.
• [ ] matches either one of the options inside the brackets:
  • {q<RF>} spawns a q snake turned 45 degrees rightward (i.e. Right and Forward) from the main snake's direction. The q snake matches if the diagonal contains exactly one queen.
  • {n<RF>} spawns an n snake instead. The n snake matches if the diagonal contains no queens.
• . matches any character, moving the match pointer forward.
• After checking as many horizontals and diagonals as possible, we verify that we're at the edge by spawning {e<>}.
• Finally, <R> turns the main snake right, ready to match the next edge.

Weird stuff

• There's nothing in the program to ensure that matching starts at an outside corner. In fact, the truthy test cases yield several matches, some of which start on the inside somewhere. Despite this, none of the falsey cases I've tried have generated any false positives.
• If I'm reading the language spec right, I should have been able to use X (branch in all diagonal directions) in place of RF. Unfortunately, the online interpreter said that was a syntax error. I also tried * (branch in all directions), but that hung the interpreter.
• Theoretically, something like _*Q?_*$ ought to work for matching "at most one queen" in the diagonals, but that also hung the interpreter. My guess is that the possibility of empty matches causes problems.

Answer 6

J, 37 bytes

(+/&,=#)*1=[:>./+//.,+//.&|.,+/,+/&|:

Anonymous function train which takes Boolean matrix as argument.

Try it online!

( +/ the sum & of , the ravel = equals # the tally of rows )

* and (lit. times)

1 one = equals [: the >./ maximum of

+/ the sums /. diagonally , and (lit. catenated to)

+/ the sums /. diagonally & of |. the reverse , and

+/ the sums across , and

+/ the sums & of |: the transpose

Answer 7

Ruby, 120 bytes

Lambda function based on the original spec that required input as a string.

->s{t=k=0
a=[]
s.bytes{|i|i>65&&(a.map{|j|t&&=((k-j)**4).imag!=0};a<<k)
k=i<11?k.real+1:k+?i.to_c}
t&&~a.size**2>s.size}

converts the Q's into complex numbers and subtracts them from each other. If the difference between the coordinates of any two queens is horizontal, vertical or diagonal, raising it to the 4th power will yield a real number and the arrangement is invalid.

Ungolfed in test program

f=->s{                                 #Take input as string argument.
  t=k=0                                #k=coordinate of character. t=0 (truthy in ruby.)
  a=[]                                 #Empty array for storing coordinates.
  s.bytes{                             #Iterate through all characters as bytes.
    |i|i>65&&(                         #If alphabetical, compare the current value of k to the contents of a
      a.map{|j|t&&=((k-j)**4).imag!=0} #If k-j is horizontal, vertical or diagonal, (k-j)**4 will be real and t will be false
      a<<k)                            #Add the new value of k to the end of a.
    k=i<11?k.real+1:k+?i.to_c          #If not a newline, increment the imaginary part of k. If a newline, set imaginary to 0 and increment real
  }                                    #s.size should be a*a + a newlines. ~a.size = -1-a.size, so ~a.size**2 = (a.size+1)**2
t&&~a.size**2>s.size}                  #compare a.size with s.size and AND the result with t. Return value. 


p f["...Q....
......Q.
..Q.....
.......Q
.Q......
....Q...
Q.......
.....Q.."]

p f["...Q.
Q....
.Q...
....Q
..Q.."]

p f["Q.
Q."]

p f["..Q
...
.Q."]

p f["..Q.
Q...
...Q
.Q.."]

p f["Q"]

Answer 8

Python 3, 232 200 155 bytes

d=1
f=input()
Q=[]
for i in f:d=[0,d][i.count('Q')==1];Q+=[(len(Q),i.index('Q'))]
print[0,d][sum(k[1]==i[1]or sum(k)==sum(i)for k in Q for i in Q)==len(Q)]

Try it online!

-32 bytes thanks to @beaker noticing a change in the input specifications; I have changed the language from Python 3 to 2, thus allowing for me to use input to take input as an array of strings or an array of character arrays.

-45 bytes thanks to @Leaky Nun

Answer 9

JavaScript (ES6), 115 bytes

a=>!a.some((b,i)=>b.some((q,j)=>q&&h[i]|v[j]|d[i+j]|e[i-j]|!(h[i]=v[j]=d[i+j]=e[i-j]=1))|!h[i],h=[],v=[],d=[],e=[])

Ungolfed:

function queens(arr) {
    horiz = [];
    vert = [];
    diag = [];
    anti = [];
    for (i = 0; i < arr.length; i++) {
        for (j = 0; j < arr.length; j++) {
            if (arr[i][j]) { // if there is a queen...
                if (horiz[i]) return false; // not already on the same row
                if (vert[j]) return false; // or column
                if (diag[i + j]) return false; // or diagonal
                if (anti[i - j]) return false; // or antidiagonal
                horiz[i] = vert[j] = diag[i + j] = anti[i - j] = true; // mark it
            }
        }
        if (!horiz[i]) return false; // fail if no queen in this row
    }
    return true;
}

Answer 10

Ruby, 155 bytes

->x{(y=x.map{|r|(i=r.index ?Q)==r.rindex(?Q)?i:p or-2}).zip(y.rotate).map.with_index{|n,i|n.max-n.min==1&&i<y.size-1?-2:n[0]}.inject(:+)*2==(s=x.size)*~-s}

This is horrible to read, so I've got a slightly less golfed version below

->x{
    (y=x.map{|r|(i=r.index ?Q)==r.rindex(?Q)?i:p or-2})
    .zip(y.rotate)
    .map.with_index{|n,i|n.max-n.min==1&&i<y.size-1?-2:n[0]}
    .inject(:+)*2==(s=x.size)*~-s
}

This is the same code, but with some newlines to separate out what's happening.

The code tself is an anonymous lambda function which takes an array of strings (x) in the format ["..Q", "Q..", ".Q."].

The first line is mapping each string to the index of the Q character in that string. If there is no Q character, it's replaced with -2¹. This new array of indices is assigned to the variable y.

The next line zips this array of indices with itself offset by one (rotated). This results in an array of pairs of consecutive indices.

The next line is particularly complicated. It goes through each of the pairs of indices, and subtracts the smaller from the larger. If this is 1 (and we're not at the last pair²), then there are two queens that are on the same diagonal, and a value of -2 is inserted, otherwise the original index of the queen in the string is inserted.

The last line sums up all the indexes for each and checks to see if it is the triangle number for n-1, where n is the width (or height) of the square.

1: -1 would have been my go-to, but it's 1 apart from 0, so would mess with the checking of diagonals. The negative-ness of it is important to make the final sum wrong. I thought about a high number (with single digits) like 9, but I can't be sure that won't result in an incorrect verification.
2: The board doesn't wrap round, whereas ruby's rotate array function does, and if the last pair is different by one it doesn't matter - that's not a diagonal.

Answer 11

PHP, 137 143 bytes

inspired by Neil´s solution

for($n=1+strlen($s=$argv[1])**.5|0;($c=$s[$p])&&!(Q==$c&&$v[$x=$p%$n]++|$h[$x=$p/$n]++|$d[$y-$x]++|$a[$y+$x]++);$p++);echo$n-1==count($a)&&!$c;

takes input from first command line argument; run with -r. Requires single byte line breaks.
^{Actually you can use any character but 0 for the line break.}
prints true (1) or false (empty string).

breakdown

for($n=1+strlen($s=$argv[1])**.5|0; // copy input to $s, $n=size+1 (for the linebreak)
    ($c=$s[$p])&&!(                 // loop through characters
        Q==$c&&                         // if queen: test and increment lines
            $v[$x=$p%$n]++|$h[$x=$p/$n]++|$d[$y-$x]++|$a[$y+$x]++
    );                                  // break if a line had been marked before
    $p++);
echo$n-1==count($a)             // print result: true for $n-1(=size) marks
    &&!$c;                      // and loop has finished

Answer 12

Python 3, 185 176 175 172 171 bytes

lambda x,c=lambda x:x.count("Q")==1:all([*map(c,x+[[l[i]for l in x]for i in range(len(x[0]))])])*~any(map(lambda s:"Q%sQ"%(s*".")in"".join(x),[len(x[0]),len(x[0])-2]))==-1

An anonymous function taking a list of strings as input.

Python 2, 175 bytes

lambda x:all([a.count("Q")==1for a in x]+[[l[i]for l in x].count("Q")==1for i in range(len(x[0]))]+[all(map(lambda s:"Q%sQ"%(s*".")not in"".join(x),[len(x[0]),len(x[0])-2]))])