2
\$\begingroup\$

Given an mxm chess board, find a minimum number of pieces of the given kind and place them on a chess board in such a way that all squares are either occupied or attacked by at least one piece.

Input

The input consists of two parameters: m, the number of squares on each side; and a letter which indicates which piece to use, according to the following key: King, Queen, Rook, Bishop, kNight. For example, an input of 8 B means that you have to find a solution for an 8x8 board with bishops.

The input will always consist of a positive integer and a valid letter. You may choose to implement a program which takes input either as command-line arguments or separated by a space on stdin; or to implement a named function/verb which takes two parameters.

Output

The output should be a chess board in the following format:

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

This is a solution for the input 8 Q. Each line is separated by a newline.

Note that every valid input has a solution.

Other points

Standard loopholes are not acceptable. In particular, since your program must handle any input, it is not sufficient to hard-code the answer for small inputs.

The particular case of this problem where Queens are used has been the subject of some investigation, and the number of Queens required for square boards is in the Online Encyclopaedia of Integer Sequences as A075324. However, that probably doesn't help you for inputs larger than 18 Q, and doesn't give you the layout for smaller cases.

As a performance constraint to prevent pure brute-force approaches, the code should output a result for 18 Q in a reasonable time (approximately 6 hours).

\$\endgroup\$
2
\$\begingroup\$

This is a fun problem, and I'm sad that it has no solution, so I made my own!

Requires arguments in the form M P where M is the size of the board and P is the code for the piece

Java - S.java - 1359 Characters

public class S{int s;String p;String e=".";String b;String t;int c;public static void main(String[]args){new S(args);}S(String[] a){s=Integer.parseInt(a[0]);p=a[1];b="";int i;if(p.equals("P")){String r="P";for(i=1;i<s;i++)r+=e;r+="\n";for(i=0;i<s;i+=3){a(r);f(p);a(r);}m(0);}if(p.equals("B")){for(i=0;i<s-1;i++){if(s/2==i)f(p);f(e);}}if(p.equals("N")){for(i=0;i<s;i+=5){f(e);f(e);f("N");f(e);f(e);}m(0);if(s%5==2|s%5==1){m(1);f(p);}}if(p.equals("R")){f(p);for(i=1;i<s;i++)f(e);}if(p.equals("K")){String k="";for(i=0;i<s;i+=3)k+=".K.";k=k.substring(0,s-1);k+=(s%3==0)?e:"K";k+="\n";for(i=0;i<s;i+=3){f(e);a(k);f(e);}m(1);if(s%3==0)f(e);else a(k);}if(p.equals("Q"))for(i=0;i<s*s;i++){try{q(i,0,new String[s][s]);}catch(Exception e){}b=t;}System.out.println(b);}void q(int d,int g,String[][] o) throws Exception{int u=0;int i;if(g==s*s|u>c){if(u<=c){c=u;t="";for(i=0;i<s;i++){for(int j=0;j<s;j++)t+=o[i][j];t+="\n";}}throw new Exception();}int r=(d/s)%s;int c=d%s;if(o[c][r]==null){for(i=0;i<s;i++){try{o[c-r+i][i]=(o[c-r+i][i]==null)?e:o[c-r+i][i];}catch(Exception e){}try{o[i][r+c-i]=(o[i][r+c-i]==null)?e:o[i][r+c-i];}catch(Exception e){}o[i][r]=(o[i][r]==null)?e:o[i][r];o[c][i]=(o[c][i]==null)?e:o[c][i];}o[c][r]="Q";u++;}q(d+1,g+1,o);}void m(int d){b=b.substring(0,(s+1)*(s-d));}void a(String d){b+=d;}void f(String f){for(int i=0;i<s;i++){b+=f;}b+="\n";}}

(Pawns are attacking from left to right)

I couldn't find any proof of the minimum of any domination problem, but my Queen's solver at 8 solves with 5 queens and the others don't seem to be doing too badly (18 queens at 25x25). Someone will have to beat my other solutions to disprove them as minimums. That probably won't be hard!

Here is my de-golfed solution, for anyone interested. It's a bit of a mess... My first thought for doing the Queen's solver was to use backtracking, but I got lazy.

Java - SimpleChessSolver.java - 3496 Characters
(There was once a version which had a whole bunch of different classes, to represent the board, squares, pieces... But it quickly got out of control and was renamed ComplicatedChessSolver.java)

public class SimpleChessSolver {
int size;
String piece;
String period = ".";
String board;
String bestBoard;
int bestCount;

    public static void main(String[] args) {
        new SimpleChessSolver(args);
    }

    SimpleChessSolver(String[] args){
        size = Integer.parseInt(args[0]);
        piece = args[1];
        board = "";
        int index;
        if (piece.equals("P")){
            String periods = "P";
            for (index = 1; index < size; index++){
                periods += period;
            }
            periods += "\n";
            for (index = 0; index < size; index += 3){
                addString(periods);
                fillRow(piece);
                addString(periods);
            }
            trimToSize(0);
        }
        if (piece.equals("B")){
            for (index = 0; index < size - 1; index++){
                if (size/2 == index){
                    fillRow(piece);
                }
                fillRow(period);
            }
        }
        if (piece.equals("N")){
            for (index = 0; index < size; index += 5){
                fillRow(period);
                fillRow(period);
                fillRow("N");
                fillRow(period);
                fillRow(period);
            }
            trimToSize(0);
            if (size%5 == 2 || size%5 == 1){
                trimToSize(1);
                fillRow(piece);
            }
        }
        if (piece.equals("R")){
            fillRow(piece);
            for (index = 1; index < size; index++){
                fillRow(period);
            }
        }
        if (piece.equals("K")){
            String kings = "";
            for (index = 0; index < size; index += 3){
                kings += ".K.";
            }
            kings = kings.substring(0, size - 1);
            kings += (size%3 == 0) ? period : "K";
            kings += "\n";
            for (index = 0; index < size; index += 3){
                fillRow(period);
                addString(kings);
                fillRow(period);
            }
            trimToSize(1);
            if (size%3 == 0) {
                fillRow(period);
            }
            else {
                addString(kings);
            }
        }
        if (piece.equals("Q")){
            for (index = 0; index < size*size; index++){
                System.out.println(bestBoard);
                System.out.println("BlankLine\n");
                try {
                    queenSolve(index, 0, new String[size][size]);
                }
                catch (Exception e) {}
            }
            System.out.println("Final Answer");
            board = bestBoard;
        }

        System.out.println(board);
    }

    void queenSolve(int start, int depth, String[][] board2D) throws Exception {
        int currentCount = 0;
        int index;
        if (depth == size*size || currentCount > bestCount){
            if (currentCount <= bestCount){
                bestCount = currentCount;
                bestBoard = "";
                for (index = 0; index < size; index++){
                    for (int jdex = 0; jdex < size; jdex++){
                        bestBoard += board2D[index][jdex];
                    }
                    bestBoard += "\n";
                }
            }
            throw new Exception();
        }
        int row = (start / size) % size;
        int col = start % size;
        if (board2D[col][row] == null){
            for (index = 0; index < size; index++){
                try{
                    board2D[col - row + index][index] = (board2D[col - row + index][index] == null) ? period : board2D[col - row + index][index];
                } catch (ArrayIndexOutOfBoundsException e) {}
                try{
                    board2D[index][row + col - index] = (board2D[index][row + col - index] == null) ? period : board2D[index][row + col - index];
                } catch (ArrayIndexOutOfBoundsException e) {}
                board2D[index][row] = (board2D[index][row] == null) ? period : board2D[index][row];
                board2D[col][index] = (board2D[col][index] == null) ? period : board2D[col][index];
            }
            board2D[col][row] = "Q";
            currentCount++;
        }
        queenSolve(start + 1, depth + 1, board2D);
    }

    void trimToSize(int additionalTrim){
        board = board.substring(0, (size + 1) * (size - additionalTrim));
    }

    void addString(String toAdd){
        board += toAdd;
    }

    void fillRow(String filler){
        for (int index = 0; index < size; index++){
            board += filler;
        }
        board += "\n";
    }

}

How it works
Other than the queens, the other solutions are very simple. The Knights, Rooks, and Bishops can all be solved by putting a straight line in the correct place. Rooks cover their whole rank, so it works to just put a line anywhere on the board. A row of knights will cover four parallel rows, two in each direction. If there is a row of bishops on approximately (+/- 0.5) the middle row, they can cover every square. A row of pawns covers the parallel rows to their immediate left and right except for the bottom square, so I put a pawn on that square to occupy it. Kings can only cover the 3x3 squares around them, so I just stick Kings such that their squares don't overlap, with overlapping kings added if I need to fill out a size%3 != 0 board.

Queens is a little trickier. My algorithm, which may not be the best, iterates over the board, so that it starts on every square, then puts a queen there. It fills in periods for every square that queen covers, then walks along the board until it finds a square not already occupied by a Q or a period. As I said, this produces the current minimum for a 8x8 board (5 Queens) and I couldn't find a reference for any other board size.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.