javarecursiondepth-first-search
Peg solitaire solution change destination
I wrote a program that solves a peg solitaire in java.
My program gets a starting board and a destination board and try to finish the game.
I have a sort of counter that count my turn because I have a destination with more the 1 peg rest and as assume that if I have to remove only 2 pegs so I can solve it in only 2 moves.
I have an board class that I create:
public class Board {
private int board[][] = new int[7][7];
public Board(String place)
{
board[0][0]=2;
board[1][0]=2;
board[5][0]=2;
board[6][0]=2;
board[0][1]=2;
board[1][1]=2;
board[5][1]=2;
board[6][1]=2;
board[0][5]=2;
board[1][5]=2;
board[5][5]=2;
board[6][5]=2;
board[0][6]=2;
board[1][6]=2;
board[5][6]=2;
board[6][6]=2;
int loca=0;//location on the string of place
for(int i=0;i<7;i++){
for(int j=0;j<7;j++){
if(board[i][j]!=2) {
if (place.charAt(loca) == 'O') {
loca++;
board[i][j] = 1;
} else if (place.charAt(loca) == '.') {
loca++;
board[i][j] = 0;
}
}
System.out.print(board[i][j]);//print for test
}
System.out.println();//print for test
}
System.out.println();
}
public Board(Board copy){
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
board[i][j]=copy.getValue(i,j);
}
}
}
public int getValue(int x, int y)
{
return board[x][y];
}
public boolean isFinished(Board destination)
{
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
if(this.getValue(i,j)!=destination.getValue(i,j))
{
return false;
}
}
}
return true;
}
public Board turn(Board board,String direction,int x,int y)
{
if(direction.equals("right"))
{
board.setValue(x,y,0);
board.setValue(x+1,y,0);
board.setValue(x+2,y,1);
return board;
}
else if(direction.equals("left"))
{
board.setValue(x,y,0);
board.setValue(x-1,y,0);
board.setValue(x-2,y,1);
return board;
}
else if(direction.equals("up"))
{
board.setValue(x,y,0);
board.setValue(x,y-1,0);
board.setValue(x,y-2,1);
return board;
}
else if(direction.equals("down"))
{
board.setValue(x,y,0);
board.setValue(x,y+1,0);
board.setValue(x,y+2,1);
return board;
}
else{
System.out.println("there is not such direction, method turn on board class");
return null;//just for caution
}
}
public boolean isLegal(int x, int y){
if(board[x][y]==2)
{
return false;
}
else{
return true;
}
}
public boolean canTurn(String direction,int x,int y){
if(direction.equals("right"))
{
if(x<5) {
if (board[x][y] == 1 && board[x + 1][y] == 1 && board[x + 2][y] == 0) {
return true;
}
}
}
else if(direction.equals("left"))
{
if(x>1) {
if (board[x][y] == 1 && board[x - 1][y] == 1 && board[x - 2][y] == 0) {
return true;
}
}
}
else if(direction.equals("up"))
{
if(y>1) {
if (board[x][y] == 1 && board[x][y - 1] == 1 && board[x][y - 2] == 0) {
return true;
}
}
}
else if(direction.equals("down"))
{
if(y<5) {
if (board[x][y] == 1 && board[x][y + 1] == 1 && board[x][y + 2] == 0) {
return true;
}
}
}
else{
System.out.println("there is not such direction, method canTurn on board class");
return false;//just for caution
}
return false;
}
public void setValue(int x, int y, int value)
{
board[x][y]=value;
}
}
and I wrote my "solver" class.
public class PegSolver {
public int peg =1;
Board destinationBoard = new Board("OOOOOOOOOOOOOOOOO..OOOOOOOOOOOOOO");
Board board = new Board("OOOOOOOOOOOOOOOO.OOOOOOOOOOOOOOOO");
public void start(){
solve(0,board);
}
public boolean solve(int turn, Board board){
Board temp = new Board(board);
if(turn>peg)
{
return false;
}
else if(turn==peg){
//todo:check if solve
if(temp.isFinished(destinationBoard))
{
System.out.println("solution");
return true;
}
else
{
return false;
}
}
else//lower then 8
{
for(int i=0;i<7;i++){
for (int j=0;j<7;j++)
{
if(board.isLegal(i,j)) {
if(board.canTurn("right",i,j) && solve(turn++, temp.turn(temp, "right", i, j)))
{
return true;
}
else if(board.canTurn("left",i,j) && solve(turn++, temp.turn(temp, "left", i, j)))
{
return true;
}
else if(board.canTurn("up",i,j) && solve(turn++, temp.turn(temp, "up", i, j)))
{
return true;
}
else if(board.canTurn("down",i,j) && solve(turn++, temp.turn(temp, "down", i, j)))
{
return true;
}
}
}
}
}
return false;
}
}
When the program finds a solution, it needs to print "solution" but for some reason my program can't find a solution even when it's a basic destination with one move.
Can someone help me please?
Solution
Please review the modified code.
Many of the changes are related to indices and directions inconsistency across the code: where x represents horizontal index and y represents vertical index: array index should be board[y][x] (and not board[x][y]).
Many "magic numbers" were changed to constants for better readability of the code.
A toString method was added to the Boardclass to print out a board state. It uses special characters to make a nice printout :
This is helpful when debugging.
public class PegSolver {
private final Board startBoard, destinationBoard;
public PegSolver(Board startBoard, Board destinationBoard) {
super();
this.startBoard = startBoard;
this.destinationBoard = destinationBoard;
}
public void start(){
solve(0,startBoard);
}
private boolean solve(int turn, Board board){
//check if solve
if(board.isFinished(destinationBoard))
{
System.out.println("solved after "+ turn +" turns");
return true;
}
for(int x=0;x<board.boardSize();x++){
for (int y=0;y<board.boardSize();y++)
{
if(board.isLegal(x,y)) {
if(board.canTurn("right",x,y)
//turn++ changed to turn+1 so turn is incremented before invoking next solve
//and avoid changing the value of turn
&& solve(turn+1, board.turn(new Board(board), "right", x, y)))
return true;
else if(board.canTurn("left",x,y)
&& solve(turn+1, board.turn(new Board(board), "left", x, y)))
return true;
else if(board.canTurn("up",x,y)
&& solve(turn+1, board.turn(new Board(board), "up", x, y)))
return true;
else if(board.canTurn("down",x,y)
&& solve(turn+1, board.turn(new Board(board), "down", x, y)))
return true;
}
}
}
return false;
}
public static void main(String[] args) {
Board[] destinationBoards = {
//by order of number of turns
new Board("OOOOOOOOOOOOOO..OOOOOOOOOOOOOOOOO"), //one right turn
new Board("OOO.OOOO.OOOOO.OOOOOOOOOOOOOOOOOO"), //right, down
new Board("OOO.OO..OOOOOO.OOOOOOOOOOOOOOOOOO"), //right, down,right
new Board("OOO.OOO.OOOOO..OOOOO.OOOOOOOOOOOO"), //right, down,right,up
new Board("OOOOOOO..OOOO...OOOO.OOOOOOOOOOOO"), //right, down,right,up,up
new Board(".OO.OOO.OOOOO...OOOO.OOOOOOOOOOOO"), //right, down,right,up,up,down
new Board(".OO.OOO.OOOOO...OOOOO..OOOOOOOOOO"), //right, down,right,up,up,down, left
new Board(".OO.OOO.OOOOO...OOOOO.OOOOO.OO.OO"), //right, down,right,up,up,down,left,up
new Board(".OO.OO..O.OOO...OOOOO.OOOOO.OO.OO"), //10 turns
new Board("..O..O.O..OOO...OOOO..OOOOO..O..O"), //15 turns
new Board(".........O................O......"), //30 turns
new Board("...................O............."), //31 turns
};
Board startBoard = new Board("OOOOOOOOOOOOOOOO.OOOOOOOOOOOOOOOO");
for(Board destinationBoard : destinationBoards ){
new PegSolver(startBoard, destinationBoard).start();
}
}
}
class Board {
//int representation of the three states of a board cell
private final static int EMPTY = 0, PEG = 1, BORDER = 2;
/*cahr representation of the three states of a board cell
special chars are used to get nice printout
todo: change board to char[][] to avoid the need for two
representations (int and char)
*/
private final static char[] CHAR_REPRESENTATION = {9898,9899,10062};
private final static char ERROR = '?';
private final int BOARD_SIZE=7, CORNER_SIZE=2;
private final int board[][] = new int[BOARD_SIZE][BOARD_SIZE];
public Board(String place) {
int loca=0;
for(int y=0;y<BOARD_SIZE;y++){
for(int x=0;x<BOARD_SIZE;x++){
if(isWithinBoard(x,y)) {
if (place.charAt(loca) == 'O') {
loca++;
board[y][x] = PEG;
} else if (place.charAt(loca) == '.') {
loca++;
board[y][x] = EMPTY;
}
}else{
board[y][x] = BORDER;
}
}
}
//for testing
//System.out.println(this);
}
//copy constructor
public Board(Board copy){
for(int x=0;x<BOARD_SIZE;x++)
{
for(int y=0;y<BOARD_SIZE;y++)
{
board[y][x]=copy.getValue(x,y);
}
}
}
public int getValue(int x, int y)
{
return board[y][x]; //and not return board[x][y];
}
public boolean isFinished(Board destination)
{
for(int i=0;i<BOARD_SIZE;i++)
{
for(int j=0;j<BOARD_SIZE;j++)
{
if(this.getValue(i,j)!=destination.getValue(i,j))
return false;
}
}
return true;
}
public Board turn(Board board,String direction,int x,int y)
{
if(direction.equals("right"))
{
board.setValue(x,y,EMPTY);
board.setValue(x+1,y,EMPTY);
board.setValue(x+2,y,PEG);
return board;
}
else if(direction.equals("left"))
{
board.setValue(x,y,EMPTY);
board.setValue(x-1,y,EMPTY);
board.setValue(x-2,y,PEG);
return board;
}
else if(direction.equals("up"))
{
board.setValue(x,y,EMPTY);
board.setValue(x,y-1,EMPTY);
board.setValue(x,y-2,PEG);
return board;
}
else if(direction.equals("down"))
{
board.setValue(x,y,EMPTY);
board.setValue(x,y+1,EMPTY);
board.setValue(x,y+2,PEG);
return board;
}
System.out.println("there is not such direction, method turn on startBoard class");
return null;
}
public boolean isLegal(int x, int y){
if(board[y][x]==BORDER) //and not if(board[x][y]==BORDER)
return false;
return true;
}
public boolean canTurn(String direction,int x,int y){
if(direction.equals("right") && x < BOARD_SIZE - 2)
{
if (board[y][x] == PEG && board[y][x + 1] == PEG && board[y][x + 2] == EMPTY)
return true;
}
else if(direction.equals("left") && x > 1)
{
if (board[y][x] == PEG && board[y][x - 1] == PEG && board[y][x - 2] == EMPTY)
return true;
}
else if(direction.equals("up") && y > 1)
{
if (board[y][x] == PEG && board[y - 1][x] == PEG && board[y - 2][x] == EMPTY)
return true;
}
else if(direction.equals("down") && y < BOARD_SIZE - 2)
{
if (board[y][x] == PEG && board[y + 1][x] == PEG && board[y + 2][x] == EMPTY)
return true;
}
return false;
}
public void setValue(int x, int y, int value)
{
board[y][x]=value; //and not board[x][y]=value;
}
//for square nxn board
public int boardSize(){
return board.length;
}
public boolean isWithinBoard(int x, int y){
//check bounds
if (x < 0 || y < 0 || x >= BOARD_SIZE || y >= BOARD_SIZE) return false;
//left top corner
if (x < CORNER_SIZE && y < CORNER_SIZE) return false;
//right top corner
if(x >= BOARD_SIZE - CORNER_SIZE && y < CORNER_SIZE) return false;
//left bottom corner
if(x < CORNER_SIZE && y >= BOARD_SIZE - CORNER_SIZE) return false;
//right bottom corner
if(x >= BOARD_SIZE - CORNER_SIZE && y >= BOARD_SIZE - CORNER_SIZE) return false;
return true;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int[] row : board) {
for(int cell : row){
if(cell<CHAR_REPRESENTATION.length && cell >= 0) {
sb.append(CHAR_REPRESENTATION[cell]);
}else{
sb.append(ERROR);
}
}
sb.append("\n"); //new line
}
return sb.toString();
}
}
Todo:
The code is working but it needs further in-depth testing and debugging.
If something is not clear, don't hesitate to ask.
- Keep numbers which appear in both columns, in J lang
- Differentiation in J
- How to reshape an array with an arbitrary size in one dimension?
- Why is Insert (fold) right associative
- Write 4 : 'x&{.&.;: y' tacitly
- Alignment issue when printing formatted prime numbers in J language
- How can I define a verb in J that applies a different verb alternately to each atom in a list?
- How to get user input in the J programming language
- How to unbox a list of boxed lists of differing lengths in J?
- How can I fix 'noun result was required' error in J?
- In j, how can I define a verb locally in one scope and pass it to a defined adverb?
- Convert boxed array to normal array?
- Read column of CSV file as array
- Replace atom in array of strings
- What does the dyad `=` do to boxed strings?
- Index of minimum element using J
- How can I take the outer product of string vectors in J?
- Building an array of verbs in J
- Reading in multidigit command line parameter
- Amend with bond to new data shows unexpected behaviour
- How to turn a table or matrix into a (flat) list in J
- How to run dissect in J?
- How to define selection using index function in J
- How to exit the J console?
- Find 4-neighbors using J
- Writing custom verbs in J
- How do I negate a selector in J lang?
- How to use arbitrary selector in interchange in J lang?
- different result once square root is added inside tacit
- Sum of arrays with repeated indices