https://www.eecs.uottawa.ca/~turcotte/teaching/iti-1121/assignments/02/index.pdf

2 Second implementation [30 marks]

Our first solution works well on very small board, but quickly becomes unusable with slightly larger boards2 . We can easily optimize our code by remarking that once a solution is sure to fail, there is no point in continuing to extend it to the end. That solution can be dropped immediately. Note that we build our solution systematically, working from left to right, top to bottom. So the positions that are above the "working line" have their neighbourhood already completely specified. If the conditions for a working solution are not met for these positions, then these conditions will not be met for any completed versions of that solution and that solution can be readily abandoned. We modify our class Solution to add the following method: 2Can you figure out why the solution takes so much time as soon as the board contains more than a few positions? 8 public boolean stillPossible(boolean nextValue): this method returns false if the current solution would be impossible to finalize into a working solution, should it be extended from its current state with the value nextValue. Note that the method returns false if extending the current solution with nextValue would never yield a working solution, and true otherwise. Returning true does not mean that the solution can necessarily be extended into a working solution. It merely means that we do not yet know if it is still possible. Note as well that this method should not modify the state of the object instance of Solution on which it is called. It does not extend that solution with nextValue, it simply indicates if such an extension would annihilate its chance of leading to a working solution. . You need to modify the method solve of the class LightsOut to take benefit of the method stillPossible and provide a more efficient implementation. A few sample runs of the updated program are shown in Appendix C.