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.
