public void dfs(int[][] board, int row) {
        if (row == board.length) {
            output(board);
            return;
        }
        for (int i = 0; i < board[0].length; ++i) {
            if (isValid(board, row, i)) {
                board[row][i] = 1;
                dfs(board, row + 1);
                board[row][i] = 0;
            }
        }
    }