public class BackTrackingAlgotrithm {

    List<List<Integer>> listOfSolutionLists = new ArrayList<>();

    public boolean solveFutoshikiCSP(FutoshikiCSP futoshikiCSP) {
        List<SimpleConstrain> constrains = futoshikiCSP.getSimpleConstrains();
        List<Integer> solutionList = futoshikiCSP.getSolutionList();
        int gameSize = futoshikiCSP.getGameSize();

        int fieldIndex = -1;
        boolean isEmpty = true;

        for(int i = 0; i < gameSize*gameSize; i++) {
            if(solutionList.get(i) == 0) {
                fieldIndex = i;
                isEmpty = false;
                break;
            }
        }

        if (isEmpty)
            return true;

        for(int num = 1; num <= gameSize; num++) {
            if(futoshikiCSP.isSafe(fieldIndex, num)) {
                solutionList.set(fieldIndex, num);
                if(solveFutoshikiCSP(new FutoshikiCSP(constrains, solutionList, gameSize))) {
                    listOfSolutionLists.add(new ArrayList<>(solutionList));
                }
                else
                    solutionList.set(fieldIndex, 0);
            }
        }

        return false;
    }
}