Algorithm Practice

[Pinzu]

Im doing some practice assignments for school but I'm not sure how to handle the amount of different states in this one, my program runs out of memory (in neatbeans) before it reaches a solution for cases where n >= 7. I'm using breadth first in my search.

Fig 1: Starting state.
Fig 2: Target state.
Fig 3: Different moves: You can either jump over one or move left and right.

Im thinking my option is to not move pieces that are already in the right place (migrated left to right, but im i'd have to think about how to implement that.

Here is my code:

package f6;

import java.util.LinkedList;
import java.util.Queue;

public class BlackWhiteBricks {
 
    private enum Color {
        BLACK, WHITE, EMPTY;
    }
 
    private static boolean isSolved(State target, State current) {
        System.out.println(current.toString());
        for (int i = 0; i < target.color.length; i++) {
            if (target.color[i] != current.color[i]) {
                return false;
            }
        }
        return true;
    }

    private static class State {
        Color[] color;
        String steps;
        int empty;
        int count;
  
        private State(int n) {
            empty = n/2;
            color = new Color[n];
            steps = "";
            count = 0;
        }
  
        private State(Color[] color, String steps, int empty, int count) {
            this.count = count;
            this.empty = empty;
            this.steps = steps;
            this.color = new  Color[color.length];
            for (int i = 0; i < color.length; i++) {
                switch (color[i]) {
                    case BLACK: this.color[i] = Color.BLACK; break;
                    case WHITE: this.color[i] = Color.WHITE; break;
                    default:    this.color[i] = Color.EMPTY; break;
                }
            }
        }
  
        @Override
        public String toString() {
        StringBuilder sb = new StringBuilder("");
            for (Color c : color) {
                switch(c) {
                    case BLACK: sb.append("[B]"); break;
                    case WHITE: sb.append("[W]"); break;
                    default: sb.append("[0]"); break;
                }
            }
            sb. append(" | ").append(steps);
            return sb.toString();
        }
  
        private boolean canJumpLeft() {
            return empty < color.length - 2;
        }
  
        private void jumpLeft() {
            color[empty] = color[empty + 2];
            color[empty + 2] = Color.EMPTY;
            steps += "[" + (empty + 2) + ">>" + empty + "]";
            empty += 2;
            count++;
        }
  
        boolean canJumpRight() {
            return empty > 1;
  
        }
  
        private void jumpRight() {
            color[empty] = color[empty - 2];
            color[empty - 2] = Color.EMPTY;
            steps += "[" + (empty - 2) + ">>" + empty + "]";
            empty -= 2;
            count++;
        }
  
        private boolean canMoveLeft() {
            return empty > 0;
        }
  
        private void moveLeft() {
            color[empty] = color[empty - 1];
            color[empty - 1] = Color.EMPTY;
            steps += "[" + (empty - 1) + ">>" + empty + "]";
            empty -= 1;
            count++;
        }
  
        private boolean canMoveRight() {
            return empty < color.length - 1;
        }
  
        private void moveRight() {
            color[empty] = color[empty + 1];
            color[empty + 1] = Color.EMPTY;
            steps += "[" + (empty + 1) + ">>" + empty + "]";
            empty += 1;
            count++;
        }
    }
 
    static int counter = 0;

    private static void solve(State start, State target) {
        Queue<State> queue = new LinkedList<>();
        State current = start;
        while (!isSolved(target, current)) {
            if (current.canMoveLeft()) {
                State s = new State(current.color, current.steps, current.empty, current.count);
                s.moveLeft();
                queue.offer(s);
            }
            if (current.canMoveRight()) {
                State s = new State(current.color, current.steps, current.empty, current.count);
                s.moveRight();
                queue.offer(s);
            }
            if (current.canJumpLeft()) {
                State s = new State(current.color, current.steps, current.empty, current.count);
                s.jumpLeft();
                queue.offer(s);
            }
            if (current.canJumpRight()) {
                State s = new State(current.color, current.steps, current.empty, current.count);
                s.jumpRight();
                queue.offer(s);
            }
            current = queue.poll();
            counter++;
            //System.out.println("counter: " + counter);
        }
        System.out.println("SOLVED: " + current.toString());
    }
 
    public static void solve(int n) {
        if (n < 3 || n%2 == 0)
            throw new IllegalArgumentException("" + n);
  
        State start = new State(n);
        State target = new State(n);
  
        for (int i = 0; i < n; i++) {
            if (i < n/2) {
                start.color[i] = Color.BLACK;
                target.color[i] = Color.WHITE;
            }
            else if (i > n/2) {
                start.color[i] = Color.WHITE;
                target.color[i] = Color.BLACK;
            }
            else {
                start.color[i] = Color.EMPTY;
                target.color[i] = Color.EMPTY;
            } 
        }
        solve(start, target);
  
    }
 
}

 

[Pinzu]

Solved the issue by getting rid of the creartion of new array objects each cycle and only allowing a brick to move forward.