package leetcode;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/sudoku-solver/
 */
public class Problem37 {
    public void solveSudoku(char[][] board) {
        // TODO
    }

    private static boolean isValid(char[][] board) {
        for (int i = 0; i < 9; i++) {
            boolean[] cols = new boolean[9];
            boolean[] rows = new boolean[9];
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    if (cols[board[i][j] - '0' - 1]) {
                        return false;
                    }
                    cols[board[i][j] - '0' - 1] = true;
                }

                if (board[j][i] != '.') {
                    if (rows[board[j][i] - '0' - 1]) {
                        return false;
                    }
                    rows[board[j][i] - '0' - 1] = true;
                }
            }
        }
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                if (!isValid(board, i, i + 3, j, j + 3)) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean isValid(char[][] board, int startRow, int endRow,
                                   int startCol, int endCol) {
        boolean[] b = new boolean[9];
        for (int i = startRow; i < endRow; i++) {
            for (int j = startCol; j < endCol; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (b[board[i][j] - '0' - 1]) {
                    return false;
                }
                if (board[i][j] != '.') {
                    b[board[i][j] - '0' - 1] = true;
                }
            }
        }
        return true;
    }

    private static void print(char[][] board) {
        for (char[] c : board) {
            System.out.println(Arrays.toString(c));
        }
    }

    public static void main(String[] args) {
        Problem37 prob = new Problem37();
        prob.solveSudoku(new char[][]{
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'},
        });
    }
}

@@ -16,34 +16,8 @@
 e;%0A%0A
-import java.util.Arrays;%0A%0A
 /**%0A
@@ -151,15 +151,612 @@
     
-// TODO
+solve(board);%0A    %7D%0A%0A    private static boolean solve(char%5B%5D%5B%5D board) %7B%0A        for (int i = 0; i %3C board.length; i++) %7B%0A            for (int j = 0; j %3C board%5Bi%5D.length; j++) %7B%0A                if (board%5Bi%5D%5Bj%5D != '.') %7B%0A                    continue;%0A                %7D%0A                for (char k = '1'; k %3C= '9'; k++) %7B%0A                    board%5Bi%5D%5Bj%5D = k;%0A                    if (isValid(board) && solve(board)) %7B%0A                        return true;%0A                    %7D%0A                    board%5Bi%5D%5Bj%5D = '.';%0A                %7D%0A                return false;%0A            %7D%0A        %7D%0A        return true;
 %0A   
@@ -2357,833 +2357,7 @@
    %7D
-%0A%0A    private static void print(char%5B%5D%5B%5D board) %7B%0A        for (char%5B%5D c : board) %7B%0A            System.out.println(Arrays.toString(c));%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem37 prob = new Problem37();%0A        prob.solveSudoku(new char%5B%5D%5B%5D%7B%0A            %7B'5', '3', '.', '.', '7', '.', '.', '.', '.'%7D,%0A            %7B'6', '.', '.', '1', '9', '5', '.', '.', '.'%7D,%0A            %7B'.', '9', '8', '.', '.', '.', '.', '6', '.'%7D,%0A            %7B'8', '.', '.', '.', '6', '.', '.', '.', '3'%7D,%0A            %7B'4', '.', '.', '8', '.', '3', '.', '.', '1'%7D,%0A            %7B'7', '.', '.', '.', '2', '.', '.', '.', '6'%7D,%0A            %7B'.', '6', '.', '.', '.', '.', '2', '8', '.'%7D,%0A            %7B'.', '.', '.', '4', '1', '9', '.', '.', '5'%7D,%0A            %7B'.', '.', '.', '.', '8', '.', '.', '7', '9'%7D,%0A        %7D);%0A    %7D
 %0A%7D%0A

Solve problem 37