Our next step is to figure out how to generate all the legal moves for a state—this will tell us what choices we have.
Create a new class Square that has two integer fields: an x coordinate from 0..4 and a y coordinate from 0..5. Create a new class Move that has a to-Square and a from-Square as fields. Now add a "moveGen" method to State that returns a list of all Moves that can be made from the state. You will want to scan the board for pieces, and then generate the moves for each piece. A Java growable vector is an easy way to save and return the moves.
Missed Opportunity: As you can see, the move generator can be quite expensive to run. It generates a lot of moves, and takes two scans: one to find pieces and one to find the moves for each piece.
A better move generator would save extra state to avoid the piece scan. It would also pre-cache data to help reduce the move scan. It would generate the moves in order from best to worst as well as it could.
Most of all, a good move generator would not generate a move until the program needed it. This lazy move generation can save lots of cycles. It is easy to build a pro-quality adversary in such a way that move generation is the main cost of execution.