How many squares are guarded by chess queens?

Question

Today marks the 15th anniversary of Garry Kasparov's defeat against Deep Blue. Speaking of chess...

Input is a string that represents an 8x8 chess board containing only empty squares (.) and queens (Q). Output the number of squares that any queen can move to the next move. Queens can move any number of squares vertically, horizontally or diagonally.

Write either a program or a function. Shortest code wins, but most inventive solution gets the most upvotes.

Examples

Input:

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

Output:

Input:

QQQQQQQQ
QQQQQQQQ
QQQQQQQQ
QQQQ.QQQ
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ

Output:

@Tim the correct output for the first test case is 36. I think you forgot to count the down-right diagonal from the second queen. — Peter Taylor, Feb 10, 2011 at 22:53
@Peter You're right, I missed that diagonal. That's what I get for trying to do a computer's job. — user475, Feb 10, 2011 at 23:06
@gnibbler The upper-left queen reaches 7 squares in each of 3 directions. Since we don't count overlaps, the other queen reaches 5 squares in each of 3 directions. (3*7+3*5=36) — user475, Feb 10, 2011 at 23:14

michele · Accepted Answer · 2017-10-27 16:10:20Z

APL, 40 characters

≢⍸a<∨/(⍳8 8)∘.{∨/⊃=/(⊢,+/,-/)¨⍺⍵}⍸a←'Q'=

⍸a←'Q'= transforms the matrix in a nested vector whose elements are the coordinates of the given queens.

(⊢,+/,-/) returns for every cell: the coordinates, their sum, their difference.

{∨/⊃=/(⊢,+/,-/)¨⍺ ⍵} returns 1 if cells ⍺ & ⍵ share one coordinate, the coordinates sum or the coordinates difference; that is gives 1 if a queen can move orizontally, vertically or diagonally from ⍺ to ⍵.

⍵∘.{∨/⊃=/(⊢,+/,-/)¨⍺⍵}⍳8 8 applies the previous function to each queen and each cell in the chessboard.

∨⌿ returns the boolean matrix of cell reachable from some queens ≢⍸a< counts the cell reachable by the queens and not already occupied by queens.

\$\begingroup\$ What language is this? \$\endgroup\$
– undergroundmonorail
Oct 27, 2017 at 6:54 — undergroundmonorail, Oct 27, 2017 at 6:54
\$\begingroup\$ Welcome to PPCG! \$\endgroup\$
– Martin Ender
Oct 27, 2017 at 7:23 — Martin Ender, Oct 27, 2017 at 7:23

gnibbler · Accepted Answer · 2011-02-10 23:49:57Z

5

Python - 125 chars

import os
s=os.read(0,99)
print sum(any('*'<s[i]!='Q'in s[i::j].split()[0]for j in(-10,-9,-8,-1,1,8,9,10))for i in range(71))

edited Feb 10, 2011 at 23:49

answered Feb 10, 2011 at 23:14

gnibbler

15.1k4 gold badges47 silver badges75 bronze badges

\$\begingroup\$ Seems not to count h1. Fill all squares except the bottom right corner and your script says 1. \$\endgroup\$
– user475
Feb 10, 2011 at 23:37
1

\$\begingroup\$ @Tim, brainfart, i thought i was counting an extra one for the newline at the end because i kept getting 37 for case 1 :) \$\endgroup\$
– gnibbler
Feb 10, 2011 at 23:45

Add a comment |

Popov · Accepted Answer · 2017-10-27 07:47:21Z

5

APL, 37 chars

{≢t~⍨⍸∨/(=/∘|∨0∘∊)¨(⍳8 8)∘.-t←⍸'Q'=⍵}

'Q'=⍵ gives boolean mask of queens
⍸ gives vector of coordinates (row, column) of queens
t← stores the result in var t
(⍳8 8)∘.- outer product: gives "distances" (∆row, ∆column) between all grid cells and queen cells
0∘∊ checks if either ∆row or ∆column is 0
=/∘| checks if ∆row = +/- ∆column
(=/∘|∨0∘∊)¨ checks both conditions for all "distances"
∨/ checks if at least one of those checks return true
⍸ gives vector of coordinates (row, column) of reachable cells
t~⍨ removes original queens' positions
≢ count

answered Oct 27, 2017 at 7:47

Popov

1891 silver badge3 bronze badges

\$\begingroup\$ Welcome to PPCG! \$\endgroup\$
– Martin Ender
Oct 27, 2017 at 8:29
\$\begingroup\$ you can save a char by computing the abs value a little earlier - right after the outer product \$\endgroup\$
– ngn
Oct 27, 2017 at 12:22

Add a comment |

Aman ZeeK Verma · Accepted Answer · 2011-02-11 01:39:13Z

Java Solution

public class NewQueenProblem {  
        public static int countMoves(String input){
            int moves=0;
            class Board{
                char data;
                boolean visited;
            }
            Board[][] board=new Board[8][8];
            int x=0;
            for (int i=0; i< 64; i++){
                board[x%8][i%8] = new Board();
                board[x%8][i%8].data=input.charAt(i);
                if ((i+1)%8==0)
                    x++;
            }
            for (int i=0; i< 8; i++){
                for (int j=0; j< 8; j++){
                    if (board[i][j].data == 'Q'){
                        for (int row=0; row<8; row++)
                            if (board[i][row].data != 'Q' && !board[i][row].visited)
                                { moves++; board[i][row].visited=true;}
                        for (int col=0; col<8; col++)
                            if (board[col][j].data != 'Q' && !board[col][j].visited)
                                { moves++; board[col][j].visited=true;}
                        int posX=i, posY=j;
                        while (posX < 8 && posY < 8){
                            if (board[posX][posY].data != 'Q' && !board[posX][posY].visited)
                            { moves++; board[posX][posY].visited=true;}
                            posX++; posY++;
                        }
                        posX=i; posY=j;
                        while (posX > 0 && posY > 0){
                            if (board[posX][posY].data != 'Q' && !board[posX][posY].visited)
                            { moves++; board[posX][posY].visited=true;}
                            posX--; posY--;
                        }
                        posX=i; posY=j;
                        while (posX > 0 && posY < 8){
                            if (board[posX][posY].data != 'Q' && !board[posX][posY].visited)
                            { moves++; board[posX][posY].visited=true;}
                            posX--; posY++;
                        }
                        posX=i; posY=j;
                        while (posX < 8 && posY > 0){
                            if (board[posX][posY].data != 'Q' && !board[posX][posY].visited)
                            { moves++; board[posX][posY].visited=true;}
                            posX++; posY--;
                        }                   
                    }
                }
            }
            return moves;
        }
public static void main(String[] args) {
        int moves = countMoves("Q................Q..............................................");
        //int moves = countMoves("QQQQQQQQQQQQQQQQQQQQQQQQQQQQ.QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ");
        System.out.println(moves);
    }
}

\$\begingroup\$ http://www.ideone.com/KFxxd oops that's ~1800 characters \$\endgroup\$
– Aman ZeeK Verma
Feb 11, 2011 at 1:44 — Aman ZeeK Verma, Feb 11, 2011 at 1:44
\$\begingroup\$ Please golf this. \$\endgroup\$
– SuperJedi224
Nov 24, 2015 at 15:57 — SuperJedi224, Nov 24, 2015 at 15:57

lstefano · Accepted Answer · 2016-06-28 15:47:51Z

APL, 50 chars

{≢(b~x)∩,(x←(,'Q'=⍵)/b←,⍳8 8)∘.+(⍳8)∘.×∘.,⍨1 0 ¯1}

In English:

∘.,⍨1 0 ¯1: computes all the pairs composed by -1, 0 or 1, i.e.: (0 0)(0 1)(0 -1)(1 0) and so on;
(⍳8)∘.×∘.,⍨1 0 ¯1: multiply all the pairs computed by all the number from 1 to 8, obtaining all the possible offsets of movement of the queen;
(x←(,'Q'=⍵)/b←,⍳8 8): puts is x the coordinates of the given queens;
∘.+: compute yet another outer sum, combining the position of the given queens with all the possible displacement offsets. This gives a multidimensional array of coordinate pairs of all the possible place where each of the queens might end up, including outside the board (whose valid coordinate pairs is in b)
(b~x)∩,: removes from the list b all the coordinates taken by the queens in the given (x) and intersects it with flattened array of pairs of all the possible positions of the queens
≢: count the remaining pairs

Try online sample 1.

Try online sample 2

The array literal at the end of your code could be 2-⍳3 if index origin is 1, 1-⍳3 if it's 0. — Adalynn, Jul 31, 2017 at 22:48

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

JavaScript 140 bytes

f=a=>a.split`
`.map((r,y,G)=>[...r].map((c,x)=>A+=c<"Q"&&G.some((R,Y)=>[...R].some((C,X)=>C>"."&&((d=X-x)*(D=Y-y)==0||d**2==D**2)))),A=0)&&A

console.log(f(`Q.......
........
.Q......
........
........
........
........
........`)==37)

console.log(f(`QQQQQQQQ
QQQQQQQQ
QQQQQQQQ
QQQQ.QQQ
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ`)==1)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 27, 2017 at 19:46

DanielIndie

1,2405 silver badges5 bronze badges

Add a comment |

Xcali · Accepted Answer · 2017-10-27 22:28:48Z

0

Perl 5, 172 + 3 (`-pF`) bytes

push@a,[@F]}{for$i(0..7){O:for$j(0..7){for$x(-1..1){for$y(-1..1){if($x|$y){$r=$i;$c=$j;$a[$i][$j]ne Q&&$a[$r][$c]eq Q&&++$\&&next O while(($r+=$x)^7)<8&&(($c+=$y)^7)<8}}}}}

Try it online!

There's got to be a better way to do it, but this at least works.

answered Oct 27, 2017 at 22:28

Xcali

13.1k2 gold badges13 silver badges35 bronze badges

Add a comment |

Stack Exchange Network

How many squares are guarded by chess queens?

Examples

7 Answers 7

APL, 40 characters

Python - 125 chars

APL, 37 chars

APL, 50 chars

JavaScript 140 bytes

Perl 5, 172 + 3 (`-pF`) bytes

Your Answer

Hot Network Questions

How many squares are guarded by chess queens?

Examples

7 Answers 7

APL, 40 characters

Python - 125 chars

APL, 37 chars

APL, 50 chars

JavaScript 140 bytes

Perl 5, 172 + 3 (-pF) bytes

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions

Perl 5, 172 + 3 (`-pF`) bytes