programming class implementation. I havebeen trying but cannot seem to get it right. I have included thetest class as well.

/*
* Copyright 2017 Marc Liberatore.
*/

package search;

import java.util.List;

/**
* An implementation of a Searcher that performs an iterativesearch,
* storing the list of next states in a Queue. This results ina
* breadth-first search.
*
* @author liberato
*
* @param the type for each vertex in the searchgraph
*/
public class Searcher {
private final SearchProblemsearchProblem;

/**
* Instantiates a searcher.
*
* @param searchProblem
* thesearch problem for which this searcher will find and
* validate solutions
*/
public Searcher(SearchProblemsearchProblem) {
this.searchProblem =searchProblem;
}

/**
* Finds and return a solution to the problem,consisting of a list of
* states.
*
* The list should start with the initial stateof the underlying problem.
* Then, it should have one or more additionalstates. Each state should be
* a successor of its predecessor. The laststate should be a goal state of
* the underlying problem.
*
* If there is no solution, then this methodshould return an empty list.
*
* @return a solution to the problem (or anempty list)
*/
public List findSolution(){
// TODO
return null;
}

/**
* Checks that a solution is valid.
*
* A valid solution consists of a list ofstates. The list should start with
* the initial state of the underlying problem.Then, it should have one or
* more additional states. Each state should bea successor of its
* predecessor. The last state should be a goalstate of the underlying
* problem.
*
* @param solution
* @return true iff this solution is a validsolution
* @throws NullPointerException
* ifsolution is null
*/
public final booleanisValidSolution(List solution) {
// TODO
return false;
}
}
Test Class:

/*
* Copyright 2017 Marc Liberatore.
*/

package search;

import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;

import mazes.Cell;
import mazes.Maze;
import mazes.MazeGenerator;

import org.junit.Before;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.Timeout;

public class SearcherTest {
// @Rule
// public Timeout globalTimeout = newTimeout(500L, TimeUnit.MILLISECONDS);

private Maze maze;

@Before
public void before() {
maze = new MazeGenerator(3,3, 2).generateDfs();
/* maze should now be:
#0#1#2#
0 S 0
# # # #
1 1
# ### #
2 G 2
#0#1#2#
*/
}

@Test
public void testIsValidSolution() {
List solution =new ArrayList();
final Searcher s= new Searcher(maze);
solution.add(new Cell(1,0));
solution.add(new Cell(0,0));
solution.add(new Cell(0,1));
solution.add(new Cell(0,2));
solution.add(new Cell(1,2));
assertTrue(s.isValidSolution(solution));
}

@Test
public voidtestSolutionStartsNotAtInitialState() {
List solution =new ArrayList();
final Searcher s= new Searcher(maze);
solution.add(new Cell(0,0));
solution.add(new Cell(0,1));
solution.add(new Cell(0,2));
solution.add(new Cell(1,2));
assertFalse(s.isValidSolution(solution));
}

@Test
public void testSolutionDoesNotReachGoal(){
List solution =new ArrayList();
final Searcher s= new Searcher(maze);
solution.add(new Cell(1,0));
solution.add(new Cell(0,0));
solution.add(new Cell(0,1));
solution.add(new Cell(0,2));
assertFalse(s.isValidSolution(solution));
}

@Test
public void testSolutionSkipsState() {
List solution =new ArrayList();
final Searcher s= new Searcher(maze);
solution.add(new Cell(1,0));
solution.add(new Cell(0,0));
solution.add(new Cell(0,2));
solution.add(new Cell(1,2));
assertFalse(s.isValidSolution(solution));
}

@Test
public void testSolutionNotAdjancentStates(){
List solution =new ArrayList();
final Searcher s= new Searcher(maze);
solution.add(new Cell(1,0));
solution.add(new Cell(1,1));
solution.add(new Cell(1,2));
assertFalse(s.isValidSolution(solution));
}

@Test
public void testSolver() {
final Searcher s= new Searcher(maze);
assertTrue(s.isValidSolution(s.findSolution()));
}
}