# Tiling an nxn grid with L-shaped Trominoes

This is some code I wrote in order to see if it was possible to tile a 9x9 grid using trominoes that are shaped like this:

_
| |_
|___|

(They can be rotated.)

One issue I had while writing this is that I had to fix too many small errors (like having a 0 instead of a -1); is there some way to reduce the number of errors?

Here is the code:

public class LTiling {
public static void main(String[] args) {
int size = 9;
int[][] board = new int[size][size];
Piece[] pieces = new Piece[size*size/3+1];
for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
board[i][j] = -1;
}
}
int minrow = 0;
int mincol = 0;
int piecenum = 0;
boolean flag = true;
while(!full(board)) {
if(minrow == size-1) {
piecenum--;
while(pieces[piecenum].state==3) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol-1] = -1;
pieces[piecenum] = null;
piecenum--;
}
if (pieces[piecenum].state == 0) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol+1] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol+1] = -1;
} else if (pieces[piecenum].state == 1) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol+1] = -1;
} else {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol+1] = -1;
}
pieces[piecenum].state++;
minrow = findMinRow(board);
mincol = findMinCol(board);
flag = false;
}
if(flag) {
pieces[piecenum] = new Piece(piecenum, 0, minrow, mincol);
} else {
flag = true;
}
if(mincol == size-1) {
pieces[piecenum].state = 3;
}
board[minrow][mincol] = piecenum;
if(pieces[piecenum].state == 0) {
if(board[minrow][mincol+1] == -1 && board[minrow+1][mincol+1] == -1) {
board[minrow][mincol+1] = piecenum;
board[minrow+1][mincol+1] = piecenum;
mincol += 2;
if(mincol >= size) {
minrow++;
mincol = 0;
}
while(board[minrow][mincol] != -1) {
if(mincol>=size-1) {
mincol = 0;
minrow++;
if(minrow == size) {
print(board);
return;
}
} else {
mincol++;
}
}
//print(board);
//System.out.println();
//System.out.println();
//System.out.println("");
} else {
pieces[piecenum].state++;
}
}
if(pieces[piecenum].state == 1) {
if(board[minrow][mincol+1] == -1 && board[minrow+1][mincol] == -1) {
board[minrow][mincol+1] = piecenum;
board[minrow+1][mincol] = piecenum;
mincol += 2;
if(mincol >= size) {
minrow++;
mincol = 0;
}
while(board[minrow][mincol] != -1) {
if(mincol>=size-1) {
mincol = 0;
minrow++;
if(minrow == size) {
print(board);
return;
}
} else {
mincol++;
}
}
//print(board);
//System.out.println();
//System.out.println();
//System.out.println("");
} else {
pieces[piecenum].state++;
}
}
if(pieces[piecenum].state == 2) {
if(board[minrow+1][mincol] == -1 && board[minrow+1][mincol+1] == -1) {
board[minrow+1][mincol] = piecenum;
board[minrow+1][mincol+1] = piecenum;
mincol++;
if(mincol >= size) {
minrow++;
mincol = 0;
}
while(board[minrow][mincol] != -1) {
if(mincol>=size-1) {
mincol = 0;
minrow++;
if(minrow == size) {
print(board);
return;
}
} else {
mincol++;
}
}
//print(board);
//System.out.println();
//System.out.println();
//System.out.println("");
} else {
pieces[piecenum].state++;
}
}
if(pieces[piecenum].state == 3) {
if(mincol != 0 && board[minrow+1][mincol] == -1 && board[minrow+1][mincol-1] == -1) {
board[minrow+1][mincol] = piecenum;
board[minrow+1][mincol-1] = piecenum;
mincol++;
if(mincol >= size) {
minrow++;
mincol = 0;
}
while(board[minrow][mincol] != -1) {
if(mincol>=size-1) {
mincol = 0;
minrow++;
if(minrow == size) {
print(board);
return;
}
} else {
mincol++;
}
}
//print(board);
//System.out.println();
//System.out.println();
//System.out.println("");
} else {
if(piecenum > 0) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
piecenum--;
while(pieces[piecenum].state==3) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol-1] = -1;
pieces[piecenum] = null;
piecenum--;
}
if (pieces[piecenum].state == 0) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol+1] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol+1] = -1;
} else if (pieces[piecenum].state == 1) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol+1] = -1;
} else {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow+1][pieces[piecenum].lowerleftcol+1] = -1;
}
pieces[piecenum].state++;
minrow = findMinRow(board);
mincol = findMinCol(board);
flag = false;
continue;
} else {
System.out.println("Impossible");
break;
}
}
}
piecenum++;
}
}
public static int findMinRow(int[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j] == -1) {
return i;
}
}
}
return -1;
}
public static int findMinCol(int[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j] == -1) {
return j;
}
}
}
return -1;
}
public static boolean full(int[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j] == -1) {
return false;
}
}
}
return true;
}
public static void print(int[][] board) {
for(int j = 0; j < board[0].length-1; j++) {
System.out.print(" _");
}
System.out.println(" _");
for(int i = 0; i < board.length-1; i++) {
System.out.print("|");
for(int j = 0; j < board[i].length-1; j++) {
if(board[i][j] == board [i+1][j]) {
System.out.print(" ");
} else {
System.out.print("_");
}
if(board[i][j] == board [i][j+1]) {
System.out.print(" ");
} else {
System.out.print("|");
}
}
if(board[i][board[i].length-1] == board[i+1][board[i].length-1]) {
System.out.print(" ");
} else {
System.out.print("_");
}
System.out.println("|");
}
System.out.print("|");
for(int j = 0; j < board[0].length-1; j++) {
System.out.print("_");
if(board[board.length-1][j] == board[board.length-1][j+1]) {
System.out.print(" ");
} else {
System.out.print("|");
}
}
System.out.print("_|");
}
public static class Piece {
/*
* State 0:
*           _
*         _|_|
*        |_|_|
*
* State 1:
*         _
*        |_|_
*        |_|_|
*
* State 2:
*         _ _
*        |_|_|
*        |_|
*
* State 3:
*       _ _
*      |_|_|
*        |_|
*
*/
public int state;
public int piecenum;
public int lowerleftrow;
public int lowerleftcol;
public Piece(int p, int s, int llr, int llc) {
state = s;
piecenum = p;
lowerleftrow = llr;
lowerleftcol = llc;
}
}
}

• @JS1 Whoops; I changed it to 17 when I wanted to see how long it would take for larger boards. I have changed it back. – alphacapture Nov 18 '16 at 11:20

This is not an extensive list, but there are several ways your naming could improved that I can see:

• The parameters for your Piece constructor don't have to be shorted to their initials if you use the this keyword. i.e.

public Piece(int piecenum, int state, int lowerleftrow, int lowerleftcol) {
this.state = state;
this.piecenum = piecenum;
this.lowerleftrow = lowerleftrow;
this.lowerleftcol = lowerleftcol;
}


What this does is reference the current object so that the fields of Piece are referenced instead of the arguments.

• You use camel case your method names (e.g. findMinRow) but not for your variable names (e.g. lowerleftrow). Apart from the fact that the most widely used naming convention for Java is CamelCase, it's good to have a consistant naming style.

• flag should be renamed to something that better explains what it is a flag for. On its own flag is not meaningful enough for anyone else to easily understand what it will be used for without having to first read through our code and look for places where it is used.

I hope this helps!

Your code has lots of duplicated code. This could be avoided by extracting repeated code to parameterized methods.

I think it was Robert C "Uncle Bob" Martin who stated: large methods are a good place for objects to hide. In that sense we surely could find some possible new classes in your long main method...

One of this "future objects" could be a State class, that knows how to translate Tile coordinates into field coordinates and also can return its following State. This would remove the two if/else if cascades completely.

then I found an odd ball solution, this is a quite unusual way to simulate an if and makes your code even harder to read:

while(pieces[piecenum].state==3) {
// ...
pieces[piecenum] = null;
// ...
}


can you tell why you did that?
BTW: this must have thrown a NullPointerException...

[EDIT] When we introduce an enum PieceState like this:

public enum PieceState {
PieceState2 {
void placeOnBoard(int[][] board, Piece[] pieces, int piecenum) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow + 1][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow + 1][pieces[piecenum].lowerleftcol + 1] = -1;
}
},
PieceState1 {
void placeOnBoard(int[][] board, Piece[] pieces, int piecenum) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow + 1][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol + 1] = -1;
}
},
PieceState0 {
void placeOnBoard(int[][] board, Piece[] pieces, int piecenum) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol + 1] = -1;
board[pieces[piecenum].lowerleftrow + 1][pieces[piecenum].lowerleftcol + 1] = -1;
}
},
PieceState3 {
void placeOnBoard(int[][] board, Piece[] pieces, int piecenum) {
board[pieces[piecenum].lowerleftrow][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow + 1][pieces[piecenum].lowerleftcol] = -1;
board[pieces[piecenum].lowerleftrow + 1][pieces[piecenum].lowerleftcol - 1] = -1;
}
};
abstract void placeOnBoard(int[][] board, Piece[] pieces, int piecenum);

PieceState getNext() {
return values()[ordinal() + 1 % values().length];
}
}


and change the Piece class a little bit like this:

public static class Piece {
/*
* State 0: _ _|_| |_|_|
*
* State 1: _ |_|_ |_|_|
*
* State 2: _ _ |_|_| |_|
*
* State 3: _ _ |_|_| |_|
*
*/
public PieceState state;
public int piecenum;
public int lowerleftrow;
public int lowerleftcol;

public Piece(int p, PieceState s, int llr, int llc) {
state = s;
piecenum = p;
lowerleftrow = llr;
lowerleftcol = llc;
}
}


then your code would change to this:

while (!full(board)) {
if (minrow == size - 1) {
piecenum--;
pieces[piecenum].state.placeOnBoard(board, pieces, piecenum);
piecenum--;
}
pieces[piecenum].state = pieces[piecenum].state.getNext();
minrow = findMinRow(board);
mincol = findMinCol(board);
flag = false;
}
if (flag) {
pieces[piecenum] = new Piece(piecenum, PieceState.PieceState0, minrow, mincol);
} else {
flag = true;
}
if (mincol == size - 1) {
pieces[piecenum].state = PieceState.PieceState3;
}
board[minrow][mincol] = piecenum;
if (pieces[piecenum].state == PieceState.PieceState0) {
// ...