6
\$\begingroup\$

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:

37

Input:

QQQQQQQQ
QQQQQQQQ
QQQQQQQQ
QQQQ.QQQ
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ

Output:

1
\$\endgroup\$
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor Feb 10 '11 at 22:53
  • \$\begingroup\$ @Peter You're right, I missed that diagonal. That's what I get for trying to do a computer's job. \$\endgroup\$ – user475 Feb 10 '11 at 23:06
  • 1
    \$\begingroup\$ I get 37 for the first test case \$\endgroup\$ – gnibbler Feb 10 '11 at 23:09
  • \$\begingroup\$ @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) \$\endgroup\$ – user475 Feb 10 '11 at 23:14
  • \$\begingroup\$ @Tim: you are forgetting about c7 (for a total of 37) \$\endgroup\$ – BlueRaja - Danny Pflughoeft Feb 10 '11 at 23:28
5
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ Seems not to count h1. Fill all squares except the bottom right corner and your script says 1. \$\endgroup\$ – user475 Feb 10 '11 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 '11 at 23:45
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What language is this? \$\endgroup\$ – undergroundmonorail Oct 27 '17 at 6:54
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Oct 27 '17 at 7:23
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Oct 27 '17 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 '17 at 12:22
3
\$\begingroup\$

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);
    }
}
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ The array literal at the end of your code could be 2-⍳3 if index origin is 1, 1-⍳3 if it's 0. \$\endgroup\$ – Zacharý Jul 31 '17 at 22:48
0
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy