BiggestArmy.java

/* https://puzzling.stackexchange.com/questions/60942/biggest-army-on-a-chessboard

Reminder
Everybody knows that we can place 8 queens in a chessboard without threatening each other (see There). same reasonment can be made for knights, bishops, rooks and kings. Giving respectively 32 knights, 14 bishops, 8 rooks, and 16 kings.
Problem
If we assign to each type of piece a value invertly proportionnal of the number of this we can place. It means Knights = 1/32. Bishop = 1/14. Rook = 1/8. Queen =1/8 and King = 1/16.

What is the best sum value we can achieve mixing these pieces still with none able to take each other?*/

/*

Brute forces each tile in turn (DFS).
The optimization on DFS is maxDensity
  - there is a maximum amount of points to be scored on average per tile over many consecutive tiles
  - For example, no more than 131/224 points can be scored on the last two rows of the board.

The values after "last 3 rows" are computed using the previous maxDensities

      ...    total   avg          row #         find method
      ... max 128 (16.0000) in last 1 row  - checked with no limit
      ... max 131 ( 8.1875) in last 2 rows - checked with no limit
      ... max 161 ( 6.7083) in last 3 rows - checked with no limit
      ... max 196 ( 6.1250) in last 4 rows - checked with maxDensities
      ... max 217 ( 5.4250) in last 5 rows - checked with maxDensities
      ... max 236 ( 4.9167) in last 6 rows - checked with maxDensities
      ... max 271 ( 4.8393) in last 7 rows - checked with maxDensities
      ... max 299 ( 4.6719) in last 8 rows - checked with maxDensities*/

import java.util.Arrays;

public class BiggestArmy {

  public static void main(String[] args){
    Solver solver = new Solver(8, 8, 224);
    solver.solve();
  }

}

class Solver {

  private int width;
  private int height;
  private int maxSoFar;
  private float scoreMult;

  private double[] maxDensities = {1000000, 16.0001, 8.1876, 6.7084, 6.1251, 5.4251, 4.9168};

  private int[][] pieces;
  private boolean[][] covered;

  public Solver(int width, int height, int scoreDiv){

    this.width = width;
    this.height = height;
    // scoreMult: 1/224 to get integer to float score
    this.scoreMult = (float) 1 / scoreDiv;

    // 224
    /* Each piece gets score out of 224:
    3 Knight: 7
    4 King: 14
    1 Bishop: 16
    2 Rook: 28
    Never use queens (rooks are superior)
    */
  }

  public void solve(){
    System.out.println("Max Densities: " + Arrays.toString(maxDensities));
    covered = new boolean[height][width];
    pieces = new int[height][width];
    maxSoFar = 0;

    solve(0, 0, 0);
  }

  private void solve(int x, int y, int boost){
    // startX and startY prevent placing pieces in different orders, same locations
    if (x >= width){
      x = 0;
      y ++;
    }

    boolean[][] old = dup(covered);
    //pieces = dup(pieces);

    // assume score density is max maxDensity points / tile
    // --> stop deepening if theres not enough points anyway
    int tilesLeft = (width * (height - y - 1) + (width - x - 1));
    if (y < height - 1 && y >= height - maxDensities.length + 1){
      if (tilesLeft * maxDensities[height - y] + boost < maxSoFar){
        return;
      }
    }

    if (y >= height){
      if (boost >= maxSoFar){
        maxSoFar = boost;

        System.out.println("maxDensities " + Arrays.toString(maxDensities));
        System.out.println("total " + boost + ", score " + boost * scoreMult);
        printPieces(pieces);
        System.out.println();
      }
      return;
    }

    boolean works;

    if(covered[y][x] || pieces[y][x] != 0){
      // nothing placed
      solve(x+1, y, boost);
      return;
    }

    tryBishop(x, y, boost);
    covered = dup(old);

    tryRook(x, y, boost);
    covered = dup(old);

    tryKnight(x, y, boost);
    covered = dup(old);

    tryKing(x, y, boost);
    covered = dup(old);

    // nothing placed
    pieces[y][x] = 0;
    solve(x+1, y, boost);
    covered = dup(old);

    // clean up
    pieces[y][x] = 0;
  }

  private void tryBishop(int x, int y, int boost){
    pieces[y][x] = 1;
    boolean works = true;
    covered[y][x] = true;
    for(int i=0; i<height; i++)
      works = works && (i == y || attempt(x+i-y, i) && attempt(x+y-i, i));
    if(works)
      solve(x+1, y, boost + 16);
  }

  private void tryRook(int x, int y, int boost){
    pieces[y][x] = 2;
    boolean works = true;
    covered[y][x] = true;
    for (int i=0; i<height; i++)
      works = works && (i == y || attempt(x, i));
    for (int i=0; i<width; i++)
      works = works && (i == x || attempt(i, y));
    if(works)
      solve(x + 1, y, boost + 28);
  }

  private void tryKnight(int x, int y, int boost){
    pieces[y][x] = 3;
    boolean works = true;
    covered[y][x] = true;
    for (int i = -1; i<=1; i+=2)
      for (int j = -2; j<=2; j+=4)
        works = works && attempt(x+i, y+j) && attempt(x+j, y+i);
    if(works)
      solve(x + 1, y, boost + 7);
  }

  private void tryKing(int x, int y, int boost){
    pieces[y][x] = 4;
    boolean works = true;
    covered[y][x] = true;
    for (int i=-1; i<=1; i++)
      for (int j=-1; j<=1; j++)
        works = works && ((i==0 && j==0) || attempt(x+i, y+j));
    if(works)
      solve(x + 1, y, boost + 14);
  }

  private boolean attempt(int x, int y){
    if (x >= 0 && y >= 0 && x < width && y < height) {
      if (pieces[y][x] != 0)
        return false;
      else
        covered[y][x] = true;
    }
    return true;
  }

  private boolean[][] dup(boolean[][] covered){
    boolean[][] out = new boolean[height][width];
    for(int i=0; i<height; i++){
      for(int j=0; j<width; j++){
        out[i][j] = covered[i][j];
      }
    }
    return out;
  }

  private void printPieces(int[][] arr){
    for(int i=0; i<height; i++){
      for(int j=0; j<width; j++){
        System.out.print(".BRNK".charAt(arr[i][j]));
        System.out.print(" ");
      }
      System.out.println();
    }
  }
}

/*

Optimal number on 8x8 chessboard: 299

maxDensities [1000000.0, 16.0001, 8.1876, 6.7084, 6.1251, 5.4251, 4.9168]
total 299, score 1.3348215
B N B N B N . K 
. . . . . . . . 
. K . K . K . K 
. . . . . . . . 
. K . K . K . K 
. . . . . . . . 
B N B N B N . N 
. . . . . . R . 

maxDensities [1000000.0, 16.0001, 8.1876, 6.7084, 6.1251, 5.4251, 4.9168]
total 299, score 1.3348215
K . N B N B N B 
. . . . . . . . 
K . K . K . K . 
. . . . . . . . 
K . K . K . K . 
. . . . . . . . 
N . N B N B N B 
. R . . . . . . 

maxDensities [1000000.0, 16.0001, 8.1876, 6.7084, 6.1251, 5.4251, 4.9168]
total 299, score 1.3348215
K . K . K . N . 
. . . . . . . R 
N . K . K . N . 
B . . . . . B . 
N . K . K . N . 
B . . . . . B . 
N . K . K . N . 
B . . . . . B . 

maxDensities [1000000.0, 16.0001, 8.1876, 6.7084, 6.1251, 5.4251, 4.9168]
total 299, score 1.3348215
. N . K . K . K 
R . . . . . . . 
. N . K . K . N 
. B . . . . . B 
. N . K . K . N 
. B . . . . . B 
. N . K . K . N 
. B . . . . . B 

*/