Solver.java

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package com.leytontaylor.bfstwiddle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 *
 * @author leyto
 */
public class Solver{
    
    public Set<String> closed = new HashSet<String>();
    public Queue<Node> q = new LinkedList<>();
    
    public Node initialNode;
    public char[] goalState;
    public String strGoal;
    
    public Solver(String initialState, String goalState){
        this.initialNode = new Node(initialState.toCharArray(), null, null);
        this.goalState = goalState.toCharArray();
        this.strGoal = goalState;
        
    }
    //BFS Traversal of the Queue q
     String BFS(){
        //Add the root node to the Queue
        q.add(this.initialNode);
        
        while(!q.isEmpty()){
            //Remove the top node in the Queue
            Node current = q.remove();
            //If current Nodes boardstate == solved board state 
            //Traverse back up the tree and record all moves applied to 
            //The parent nodes
            if(String.valueOf(current.boardState).equals(strGoal)){
                return genPreviousMoves(current);

            }else{
                //Add current board state to the HashMap of already
                //Visited board states
                closed.add(String.valueOf(current.boardState));
                //Create all children of node by applying the eight legal moves
                List<Node> children=createChildren(current);
                for(Node n:children){
                    //If closed contains the board state of the child
                    //Don't add the child to the Queue
                    if(closed.contains(String.valueOf(n.boardState)))
                        continue;
                    closed.add(String.valueOf(n.boardState));
                    q.add(n);
                        
                    
                }
                
                

            }
        }return null;

    }
     
     
    //Generates a String of previos moves to the node
    String genPreviousMoves(Node n){
        List<Node> parentNodes= new LinkedList();
        parentNodes.add(n);
        //Add all parents to parentNodes
        while(n.hasParent()){
            parentNodes.add(n.getParent());
            n=n.getParent();
        }
        
        String[] prevMoves = new String[parentNodes.size()];
        //collect the sequence of prev moves 
        for(int i=0; i<parentNodes.size(); i++){
            prevMoves[parentNodes.size()-1 -i]= parentNodes.get(i).prevMove;
        }
        String moveSeq = Arrays.toString(prevMoves);
        String Solution= ("This Board can be solved by"+"\n"+
                "First Move: "+ moveSeq+"\n"+
                "Considered a total of "+Integer.toString(closed.size())+"\n"+
        
                "Fringe Still contains "+Integer.toString(q.size()));
        
        return Solution;
    }
    
    
    //created ArrayList of Nodes generated by doing all moves on 
    //the rootNode
    private List<Node> createChildren(Node rootNode) {
        List<Node> children = new ArrayList<>();
        children.add(rootNode.rotAc());
        children.add(rootNode.rotAcc());
        children.add(rootNode.rotBc());
        children.add(rootNode.rotBcc());
        children.add(rootNode.rotCc());
        children.add(rootNode.rotCcc());
        children.add(rootNode.rotDc());
        children.add(rootNode.rotDcc());
        
        return children;
        
    }
}