package org.excuseme.sudokusolver;

import java.time.Instant;
import java.time.temporal.ChronoUnit;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class DepthFirstSudokuPuzzleSolver {
    public static final String[][] PUZZLE_A = new String[][]
            {
                    {"", "", "", "2", "6", "", "7", "", "1"},
                    {"6", "8", "", "", "7", "", "", "9", ""},
                    {"1", "9", "", "", "", "4", "5", "", ""},
                    {"8", "2", "", "1", "", "", "", "4", ""},
                    {"", "", "4", "6", "", "2", "9", "", ""},
                    {"", "5", "", "", "", "3", "", "2", "8"},
                    {"", "", "9", "3", "", "", "", "7", "4"},
                    {"", "4", "", "", "5", "", "", "3", "6"},
                    {"7", "", "3", "", "1", "8", "", "", ""},
            };
    public static final String[][] PUZZLE_B = new String[][]
            {
                    {"","K","","",   "N","O","","",     "","","A","J",   "","","","E"},
                    {"","","","",   "","","","",     "","","","",   "","","",""},
                    {"F","L","","",   "","I","A","K",     "","","","O",   "B","J","P","H"},
                    {"H","","","",   "F","B","","",     "C","","P","",   "I","N","L","D"},

                    {"","","","",   "","","","",     "","","","",         "","","",""},
                    {"","D","","",   "J","F","","E",     "H","P","K","A",   "L","I","C",""},
                    {"","J","C","",   "K","","","D",     "I","B","M","L",   "E","","A",""},
                    {"I","B","M","",   "","","","N",     "E","","","",   "","","J","F"},

                    {"","O","B","K",   "I","","P","A",     "L","","H","D",   "","","E","M"},
                    {"","C","","",   "","H","","",     "K","","N","F",   "A","","",""},
                    {"","","","",   "","","","",     "","","","",   "","","",""},
                    {"J","","","",   "","","","",     "","","","",   "","","","I"},

                    {"","","","",   "B","","","",     "","L","","",   "J","","",""},
                    {"","I","","",   "A","N","H","J",     "M","D","E","C",   "F","","","O"},
                    {"N","","","",   "D","","","",     "A","","","",   "","","",""},
                    {"","","D","",   "L","","","M",     "J","","I","",   "P","","B","K"}
            };
    public static void main(String[] args) {
        final PrettyPrinter prettyPrinter = new PrettyPrinter(System.out);
        Instant starts = Instant.now();
        int length = 16;

        String[][] solution = new DepthFirstSudokuPuzzleSolver("123456789".toUpperCase().toCharArray()).solve(PUZZLE_A);
        Instant ends = Instant.now();

        prettyPrinter.print(solution);
        System.out.println("Executed in : "+ ChronoUnit.MILLIS.between(starts, ends) + " ms");

    }
    private final char[] characters;

    public DepthFirstSudokuPuzzleSolver(char[] characters) {
        this.characters = characters;
    }

    private String[][] solve(String[][] puzzle) {
        return solveRecursive(puzzle, 0, 0);
    }

    private String[][] solveRecursive(String[][] puzzle, int startRow, int startColumn) {
        for (int row = startRow; row < puzzle.length; row++) {
            for (int column = startColumn; column < puzzle.length; column++) {
                final String cellValue = puzzle[row][column];
                if (Objects.equals(cellValue, "")) {
                    final List<String> possibleValues = getPossibleValues(puzzle, row, column);
                    if (!possibleValues.isEmpty()) {
                        for (String possibleValue : possibleValues) {
                            String[][] modifiedPuzzle = cloneArray(puzzle);
                            modifiedPuzzle[row][column] = possibleValue;
                            int newColumn = column + 1;
                            int newRow = row;

                            if (newColumn == puzzle.length) {
                                newColumn = 0;
                                newRow++;
                            }

                            final String[][] solution = solveRecursive(modifiedPuzzle, newRow, newColumn);
                            if (solution != null) {
                                return solution;
                            }
                        }
                    }
                    return null;
                }
            }
            startColumn = 0;
        }
        return puzzle;
    }


    private List<String> getRowValues(String[][] puzzle, int row) {
        final List<String> integers = new ArrayList<>();
        for (String value : puzzle[row]) {
            integers.add(value);
        }
        return integers;
    }

    private List<String> getColumnValues(String[][] puzzle, int column) {
        final List<String> columnValues = new ArrayList<>();
        for (int y = 0; y < puzzle.length; y++) {
            columnValues.add(puzzle[y][column]);
        }
        return columnValues;
    }

    private List<String> getBlockValues(String[][] puzzle, int row, int column) {
        final List<String> columnValues = new ArrayList<>();
        final int sr = (int) Math.sqrt(puzzle.length);
        int blockStartColumn = column - (column % sr);
        int blockStartRow = row - (row % sr);
        for (int indexRow = blockStartRow; indexRow < blockStartRow + sr; indexRow++) {
            for (int indexColumn = blockStartColumn; indexColumn < blockStartColumn + sr; indexColumn++) {
                columnValues.add(puzzle[indexRow][indexColumn]);
            }
        }
        return columnValues;
    }

    private List<String> getPossibleValues(String[][] puzzle, int row, int column) {
        Stream<String> cStream = IntStream.range(0, characters.length).mapToObj(i ->String.valueOf(characters[i]));
        final List<String> characters = new ArrayList<String>(cStream.collect(Collectors.toList()));
        final List<String> rowValues = getRowValues(puzzle, row);
        characters.removeAll(rowValues);
        final List<String> columnValues = getColumnValues(puzzle, column);
        characters.removeAll(columnValues);
        final List<String> blockValues = getBlockValues(puzzle, row, column);
        characters.removeAll(blockValues);
        return characters;
    }

    private static String[][] cloneArray(String[][] src) {
        int length = src.length;
        String[][] target = new String[length][src[0].length];
        for (int i = 0; i < length; i++) {
            System.arraycopy(src[i], 0, target[i], 0, src[i].length);
        }
        return target;
    }
}